hdu 2844 Coins
典型的多重背包转化01背包和多重背包问题#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef __int64 LL; const int MAXN = 100010; int dp[MAXN], n, m; int AA[105]; // dp[i][j] = dp[i-1][j] || dp[i-1][j-w]; void oneBack(int w) { for (int j = m; j >= w; --j) dp[j] = dp[j]||dp[j-w]; } void comBack(int w) { for (int j = w; j <= m; ++j) dp[j] = dp[j]||dp[j-w]; } void solve() { memset(dp, 0, sizeof dp); dp[0] = 1; for (int i = 1; i<= n; ++i) scanf("%d", AA+i); for (int i = 1; i<= n; ++i) { int p, u; scanf("%d", &p); if (p*AA[i] >= m) { comBack(AA[i]); continue; } for (int o=1; o<=p; o<<=1) { u = o*AA[i]; if (u <= m) oneBack(u); p -= o; } if (p > 0 && (u=p*AA[i]) <= m) oneBack(u); } int res = 0; for (int i = m; i>0; --i) res += dp[i]; printf("%d\n", res); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif // ONLINE_JUDGE while (scanf("%d%d", &n, &m) && (n+m)) { solve(); } return 0; }
hdu 1171 Big Event in HDU
如果能一眼看出是背包问题剩下的就是套模板，以后碰到类似于就将数组分成两部分且差值最小的题可以借鉴#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef __int64 LL; const int MAXN = 1010; int dp[5005*50], n, m; int da[MAXN][2]; void oneBack(int w, int v) { for (int j = m; j >= w; --j) { if (dp[j] < dp[j-w]+v) dp[j] = dp[j-w]+v; } } void comBack(int w, int v) { for (int j = w; j <= m; ++j) { if (dp[j] < dp[j-w]+v) dp[j] = dp[j-w]+v; } } void solve() { memset(dp, 0, sizeof dp); m = 0; for (int i = 1; i<= n; ++i) scanf("%d%d", &da[i][0], &da[i][1]), m += da[i][0]*da[i][1]; int s = m; m /= 2; for (int i = 1; i<= n; ++i) { int p = da[i][0], a = da[i][1], u; if (p*a >= m) { comBack(p, p); continue; } for (int o=1; o<=a; o<<=1) { u = o*p; oneBack(u, u); a -= o; } if (a > 0 && (u=a*p) <= m) oneBack(u, u); } printf("%d %d\n", s-dp[m], dp[m]); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif // ONLINE_JUDGE while (scanf("%d", &n) && n>0) { solve(); } return 0; }
hdu 3591 The trouble of Xiaoqian
题意：给出你拥有的硬币的面值和数量，店家有相同的面值且不限数量的硬币。用这些硬币去买一固定价值的物品，给予和找回的硬币总数最小。给予店家的硬币总值不超过20000。设m=min(20000, 所有硬币的总价值)m<物品价值，则不可能将操作给予和找回两步：先正向计算出给予[0,m]价值的硬币所需最小数量dp[i][j] = min(dp[i-1][j], dp[i-1][j-w]+v);（多重背包）逆向算出最终给予[0,m]价值的硬币所需最小数量。dp[i][j] = min(dp[i-1][j], dp[i-1][j+w]+1)dp[i][j] = min(dp[i][j], dp[i][j+w]+1)#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef __int64 LL; const int MAXN = 105, INF = 0x3f3f3f3f; int n, t; int V[MAXN], C[MAXN], dp0[20005]; void oneBack(int w, int v, int all) { for (int j = all; j >= w; --j) dp0[j] = min(dp0[j], dp0[j-w]+v); } void comBack(int w, int v, int all) { for (int j = w; j <= all; ++j) dp0[j] = min(dp0[j], dp0[j-w]+v); } void comBack_(int w, int v, int all) { for (int j = all-w; j >= 0; --j) dp0[j] = min(dp0[j], dp0[j+w]+v); } void solve() { memset(dp0, INF, sizeof dp0); dp0[0] = 0; int m = 0; for (int i = 1; i<= n; ++i) scanf("%d", V+i); for (int i = 1; i<= n; ++i) scanf("%d", C+i), m+=C[i]*V[i]; m = min(20000, m); if (m < t) { printf("-1\n"); return; } // dp0[i][j] = min(dp0[i-1][j], dp0[i-1][j-w]+1); j==[0,m] for (int i = 1; i<= n; ++i) { int p = V[i], a = C[i], u; if (p*a >= m) { comBack(p, 1, m); continue; } for (int o=1; o<a; o<<=1) { u = o*p; oneBack(u, o, m); a -= o; } if ((u=a*p) <= m) oneBack(u, a, m); } dp0[0] = INF; for (int i = 1; i<= n; ++i) { comBack_(V[i], 1, m); } if (dp0[t] == INF) printf("-1\n"); else printf("%d\n", dp0[t]); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif // ONLINE_JUDGE int cs = 0; while (scanf("%d%d", &n, &t) && (n+t)) { printf("Case %d: ", ++cs); solve(); } return 0; }
hdu 1963 Investment
比较明显的多重背包问题，顺着题意来就好了#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef __int64 LL; const int MAXN = 45500; int n, t, dp[MAXN], sm, m; void comBack(int cost, int val, int all) { for (int i = cost; i<= all; ++i) dp[i] = max(dp[i], dp[i-cost]+val); } int A[15], B[15]; // O(n) = 40*10*45500 void solve() { int q; scanf("%d%d", &n, &m); scanf("%d", &q); for (int i = 0; i< q; ++i) scanf("%d%d", A+i, B+i); sm = n; while (m--) { memset(dp, 0, 4*(sm/1000+10)); for (int i = 0; i< q; ++i) comBack(A[i]/1000, B[i], sm/1000); sm += dp[sm/1000]; } printf("%d\n", sm); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif // ONLINE_JUDGE int t; scanf("%d", &t); while (t--) { solve(); } return 0; }
hdu 3496 Watch The Movie
dp[n][m][l] = max(dp[n-1][m][l], dp[n-1][m-1][l-w]+v)这题里有几个注意点：已经指出了n种电影中选正好m个，所以状态转移需要考虑前一个状态能否达到m-1个该dp中l表示小于等于l，所以初始状态中dp[0][0][0~l]置零（若采用l表示正好为l，则仅需将dp[0][0][0]置零，最终结
果要在dp[n][m] [0~l]中取最大值）#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef __int64 LL; const int MAXN = 1002; int dp[102][MAXN]; int n, m, l; // dp[n][m][l] = max(dp[n-1][m][l], dp[n-1][m-1][l-w]+v) void oneBack(int cost, int val) { for (int j = m; j>0; --j) for (int i = l; i>= cost; --i) if (dp[j-1][i-cost]!=-1) dp[j][i] = max(dp[j][i], dp[j-1][i-cost]+val); } void solve() { scanf("%d%d%d", &n, &m, &l); memset(dp, -1, sizeof dp); memset(dp[0], 0, 4*MAXN); for (int i = 0; i< n; ++i) { int a, b; scanf("%d%d", &a, &b); oneBack(a, b); } printf("%d\n", dp[m][l]==-1?0:dp[m][l]); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif // ONLINE_JUDGE int t; scanf("%d", &t); while (t--) { solve(); } return 0; }