1.比如说f[14] = f[9] + f[4] + f[1] = 3f[9] = 1 故 f[14] = 1 + f[14 - 9] = 1 + f[5] = 1 + f[4] + f[1]可以得到f[n] = f[n - j * j] + 1这个状态又例如f[13] = f[9] + f[4] = 2初始化所有值为很大的正数 因为要取min 如果设为0就会一直取0初始化f[0] = 0 #include <algorithm> #include <cstring> #include <iostream> using namespace std; con...

#include <algorithm> #include <cstring> #include <iostream> using namespace std; const int N = 1010; int f[N], w[N], v[N]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i]; for(int i = 1; i ...

求背包容量恰好被装满时，最大价值为多少？需要将数组设置为很小的负数，这样表示状态不可达设置f[0] = 0表示背包容量为0是物体价值为0，初始化 #include <algorithm> #include <cstring> #include <iostream> using namespace std; const int N = 1010; int v[N], w[N], f[N], g[N]; int main() { int n, m; cin >> n >> m; for (int i = 1;...

#include <iostream> using namespace std; // b点坐标和马的坐标 int xb, yb, xh, yh; // h为能否走的表示 long long h[30][30] = {0}, f[30][30] = {0}; int main() { cin >> xb >> yb >> xh >> yh; // 防止马在边界 xb += 2, yb += 2, xh += 2, yh += 2; // 马脚和马的位置设为1 不可走 h[xh][yh] = ...

#include <cstring> #include <iostream> using namespace std; int main() { int n; cin >> n; int f[n + 1]; memset(f, 0, sizeof f); f[1] = f[0] = 1; for(int i = 2; i <= n; i ++){ for(int j = 1; j <= i; j ++){ f[i] += f[j - 1] * f[i - j...

#include <cstring> #include <iostream> using namespace std; int main() { int n; cin >> n; int a[n], f[n], g[n]; for(int i = 0; i < n; i ++){ cin >> a[i]; } memset(f, 0, sizeof f); memset(g, 0, sizeof g); if(a[0] > 0) f[0] = 1; ...

#include <algorithm> #include <iostream> #include<vector> #include<cstring> using namespace std; int main() { int n; cin >> n; int f[n]; vector<pair<int, int>> e(n); for(int i = 0; i < n; i ++) cin >> e[i].first >> e[i].sec...

#include <iostream>using namespace std;const int N = 100010;int a[N], f[N], g[N];int main() {int n;cin >> n; for(int i = 0; i < n; i ++){ cin >> a[i]; f[i] = a[i]; g[i] = a[i]; } int sum = a[0], minN = 0, maxN = a[0]; for(int i = 1; i < n; i ++){ f[i] = ma...

考虑负负得正情况比如 -6 * -4 = 24 -2 * -4 = 8 所以也要取min #include <iostream> #include<vector> #include<algorithm> using namespace std; const int N = 2 * 100010; int f[N], g[N]; int main() { int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i ++){ ...

分类讨论 环形结构 #include <iostream> using namespace std; const int N = 2 * 100010; int a[N], dp[N]; int main() { int n; cin >> n; for(int i = 0; i < n; i ++) cin >> a[i]; dp[0] = a[0], dp[1] = a[1], dp[2] = a[2]; // 不包含第一家 从第二家到最后一家 for(int i = 3; i < n; i...

#include <iostream> #include<vector> #include<algorithm> using namespace std; const int val = 10000; int main() { int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i ++) cin >> a[i]; vector<long long> count(val, 0); int m...

#include <iostream> #include<cstring> using namespace std; const int N = 1010; int f[N][N]; char a[N], b[N]; int main() { cin >> a + 1; cin >> b + 1; int n = strlen(a + 1), m = strlen(b + 1); for(int i = 0; i <= n; i ++) f[i][0] = i; for(int i = 0; i &...

#include <iostream> using namespace std; const int N = 100010; int a[N]; int main() { int n; cin >> n; for(int i = 0; i < n; i ++){ cin >> a[i]; } int minPrice = 1e9, maxProfit = -1e9; for(int i = 0; i < n; i ++){ minPrice = min(a[i],...

#include <iostream> #include<cstring> using namespace std; const int N = 100010; int a[N], f[N]; int minJump(int n){ if(n == 0) return -1; f[0] = 0; for(int i = 0; i < n; i ++){ if(f[i] != -1){ int maxReach = min(i + a[i], n - 1); for(int ...