标准01背包一共有 N 件物品编号 \(1,2,\dots,N\)。 对于每件物品 i\(1\le i\le N\)重量为 \(w_i\)价值为 \(v_i\)。太郎打算从中挑选若干物品装进背包带走。背包的容量为 W即所选物品的总重量不能超过 W。 请求出太郎能带走的物品总价值的最大值。#include iostream #include algorithm using namespace std; typedef long long ll; const int MAXW 100005; ll dp[MAXW]; int main() { int N, W; cin N W; for (int i 1; i N; i) { int w; ll v; cin w v; // 01背包逆序 for (int j W; j w; --j) { dp[j] max(dp[j], dp[j - w] v); } } cout dp[W] endl; return 0; }变式01背包容量重量极大无法开数组维护但是价值和数量乘积非常小反向维护价值的最小重量#includebits/stdc.h using namespace std; using ll long long; const int MAXV 100005; const ll INF 1e18; ll dp[MAXV]; int main() { int N; ll W; cin N W; fill(dp, dp MAXV, INF); dp[0] 0; int sumV 0; for(int i 1; i N; i) { ll w; int v; cin w v; sumV v; for(int j sumV; j v; --j) { dp[j] min(dp[j], dp[j - v] w); } } int ans 0; for(int x sumV; x 0; --x) { if(dp[x] W) { ans x; break; } } cout ans endl; return 0; }DAG 最长路径拓扑排序 DP#includebits/stdc.h using namespace std; // 最大节点数 1e510 const int MAXN 100010; // 邻接表存图g[u] 保存u所有能到达的点 vectorint g[MAXN]; // in[v]节点v的入度 int in[MAXN]; // dp[u]以u为终点的最长路径边数 int dp[MAXN]; int n, m; int main(){ // 加速cin、cout ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; // 读入m条有向边 x - y for(int i 1; i m; i){ int x, y; cin x y; g[x].push_back(y); // y的入度1 in[y]; } // Kahn拓扑排序用队列 queueint q; // 将所有入度为0的起点入队 for(int i 1; i n; i){ if(in[i] 0){ q.push(i); } } int ans 0; // 记录全局最长路径长度 while(!q.empty()){ int u q.front(); q.pop(); // 更新全局最大值 ans max(ans, dp[u]); // 遍历u所有出边 u - v for(int v : g[u]){ // 用u的路径延长一条边更新v dp[v] max(dp[v], dp[u] 1); // u处理完毕v的一个前驱完成入度减1 in[v]--; // v所有前驱都处理完入队等待计算 if(in[v] 0){ q.push(v); } } } cout ans endl; return 0; }最长上升子序列#includebits/stdc.h using namespace std; int a[1005],dp[1005]; int main(){ int n,ans0;cinn; for(int i1;in;i) cina[i],dp[i]1; for(int i1;in;i){ for(int j1;ji;j){ if(a[j]a[i]) dp[i]max(dp[i],dp[j]1); } ansmax(ans,dp[i]); } coutans; }最大连续子段和#includebits/stdc.h using namespace std; typedef long long ll; int main(){ int n;cinn; vectorlla(n); for(int i0;in;i)cina[i]; ll dpa[0],resa[0]; for(int i1;in;i){ dpmax(a[i],dpa[i]); resmax(res,dp); } coutres; return 0; }最长公共子序列#include iostream #include string #include algorithm using namespace std; const int MAXN 3005; int dp[MAXN][MAXN]; int main() { string s, t; cin s t; int n s.size(), m t.size(); for (int i 1; i n; i) { for (int j 1; j m; j) { if (s[i-1] t[j-1]) { dp[i][j] dp[i-1][j-1] 1; } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]); } } } string res; int i n, j m; while (i 0 j 0) { if (s[i-1] t[j-1]) { res.push_back(s[i-1]); i--; j--; } else { if (dp[i-1][j] dp[i][j-1]) i--; else j--; } } reverse(res.begin(), res.end()); cout res endl; return 0; }