动态规划小白刷题（也就写写水题骗骗自己了）

目录01背包问题完全背包问题P1216 [IOI 1994 / USACO1.5] 数字三角形 Number TrianglesP1048 [NOIP 2005 普及组] 采药P1616 疯狂的采药01背包问题#include bits/stdc.h using namespace std; int n, v; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n v; vectorint weight(n), val(n); vectorint dp(v 1); for (int i 0; i n; i) cin weight[i] val[i]; for (int i 0; i n; i) for (int j v; j weight[i]; j--) dp[j] max(dp[j], dp[j - weight[i]] val[i]); cout dp[v]; return 0; }完全背包问题#include bits/stdc.h using namespace std; int n, v; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n v; vectorint weight(n), val(n); vectorint dp(v 1); for (int i 0; i n; i) cin weight[i] val[i]; for (int i 0; i n; i) for (int j weight[i]; j v; j) dp[j] max(dp[j], dp[j - weight[i]] val[i]); cout dp[v]; return 0; }P1216 [IOI 1994 / USACO1.5] 数字三角形 Number Triangles二维状态比较清楚#include bits/stdc.h using namespace std; int r; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin r; vectorvectorint gra(r 1, vectorint(r 1)); vectorvectorint dp(r 1, vectorint(r 1)); for (int i 1; i r; i) { for (int j 1; j i; j) { cin gra[i][j]; } } for (int i 1; i r; i) { dp[i][1] gra[i][1] dp[i - 1][1]; } for (int i 2; i r; i) { for (int j 2; j i; j) { dp[i][j] max(dp[i - 1][j - 1] gra[i][j], dp[i - 1][j] gra[i][j]); } } int ans 0; for (int i 1; i r; i) { ans max(ans, dp[r][i]); } cout ans; return 0; }一维DP自底向上递推#include bits/stdc.h using namespace std; int r; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin r; vectorint dp(r 1); vectorvectorint gra(r 1, vectorint(r 1)); for (int i 1; i r; i) for (int j 1; j i; j) cin gra[i][j]; for (int j 1; j r; j) dp[j] gra[r][j]; for (int i r - 1; i 1; i--) for (int j 1; j i; j) dp[j] gra[i][j] max(dp[j], dp[j 1]); cout dp[1]; return 0; }P1048 [NOIP 2005 普及组] 采药01背包模板#include bits/stdc.h using namespace std; int T, M; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin T M; vectorint time(M), value(M); for (int i 0; i M; i) cin time[i] value[i]; vectorint dp(T 1); for (int i 0; i M; i) for (int j T; j time[i]; j--) dp[j] max(dp[j], dp[j - time[i]] value[i]); cout dp[T]; return 0; }P1616 疯狂的采药完全背包模板#include bits/stdc.h using namespace std; #define int long long int t, m; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin t m; vectorint time(m), val(m); for (int i 0; i m; i) cin time[i] val[i]; vectorint dp(t 1); for (int i 0; i m; i) for (int j time[i]; j t; j) dp[j] max(dp[j], dp[j - time[i]] val[i]); cout dp[t]; return 0; }