2017年ACM模板（常用）弱渣整理 四、动态规划

一、数字三角形问题：

for(int i=1;i<=n;i++) { d[n][i] = a[n][i];//从边界出发的最大值就是其本身 } for(int i=n-1;i>=1;i--) { for(int j=1;j<=i;j++) { d[i][j] = a[i][j]+max(d[i+1][j],d[i+1][j+1]); } }

---

二、最长递增子序列：

for(int i=0;i<strlen(a);i++) { dp[i] = 1; for(int j=0;j<=i;j++) { if(a[j]<a[i]) { dp[i] = max(dp[i],dp[j]+1); } } }

---

三、最长公共子序列：

for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(s1[i] == s2[j]) { dp[i+1][j+1] = dp[i][j] + 1; }else{ dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]); } }

---

四、硬币问题：

minv[0] = maxv[0] = 0; for(int i=1; i<=s; i++) { minv[i] = INF; maxv[i] = -INF; } for(int i=1; i<=s; i++) { for(int j=1; j<=n; j++) { if(i >= V[j]) { minv[i] = min(minv[i],minv[i-V[j]]+1); maxv[i] = max(maxv[i],maxv[i-V[j]]+1); } } }

---

五、多重部分和问题：

void solve() { dp[0][0] = true;//没有数字加和当然为0了 for(int i=0;i<n;i++) { for(int j=0;j<=K;j++) { for(int k=0;k<=m[i]&&k*a[i]<=j;k++) { dp[i+1][j] |= dp[i][j-k*a[i]];//"|="为位操作运算符——位或 } } } if(dp[n][K]) printf("Yes\n"); else printf("No\n"); }

六、01背包

void solve(int w,int c) { ffor(int i=0;i<n;i++) { for(int j=0;j<=k;j++) { if(j<w[i]) dp[i+1][j] = dp[i][j];//无法挑选这个物品 else dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]); } } printf("%d\n",dp[n][k]); }

七、完全背包

void solve() { for(int i=0; i<N; i++) { for(int j=0; j<=W; j++) { for(int k=0; k*w[i]<=j; k++) { dp[i+1][j] = max(dp[i+1][j], dp[i][j-k*w[i]]+k*v[i]); } } } printf("%d\n",dp[N][W]); }

八、多重背包

#include<cstdio> #include<algorithm> using namespace std; const int maxn = 100+10; int N,W; int w[maxn], v[maxn], a[maxn]; int dp[maxn]; /*01背包*/ void zero_pack(int w, int v) { for(int j=W; j>=w; j--) { dp[j] = max(dp[j], dp[j-w]+v); } } /*完全背包*/ void comp_pack(int w, int v) { for(int j=w; j<=W; j++) { dp[j] = max(dp[j], dp[j-w]+v); } } /*多重背包*/ void mult_pack(int w, int v, int a) { //如果某件物品的数量乘以重量大于等于W，那么这个物品的最优解就直接用完全背包来推。 if(w * a >= W) { comp_pack(w, v); return; } int k = 1; while(k < a) { zero_pack(k*w, k*v); a = a - k; k = k*2; } //剩余的再需要一次01背包 zero_pack(a*w, a*v); } int main() { scanf("%d%d",&N, &W); for(int i=0; i<N; i++) { scanf("%d%d%d",&w[i],&v[i],&a[i]); } for(int i=0; i<N; i++) { mult_pack(w[i], v[i], a[i]); } printf("%d\n",dp[W]); return 0; }