和以前做的差不多
n《=10 很容易忘状态压缩那里想
预处理一下 哪几个物品可以一次运完 可以的话用一个二进制表示 并且dp[state] = 1 表示一次就可以
然后平常那样做状态压缩DP就行了
#include <cstdio> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn = 12; const int INF = 999999999; int n, m1, m2; int a[maxn]; int b[1<<maxn]; int dp[1<<maxn]; bool d[1<<maxn]; bool ok(int x) { int sum = 0; memset(d, false, sizeof(d)); d[0] = true; for(int i = 0; i < n; i++) { if(x&(1<<i)) { sum += a[i]; for(int j = m1; j >= a[i]; j--) d[j] |= d[j-a[i]]; } } for(int i = 0; i <= m1; i++) { if(d[i] && sum-i <= m2) return true; } return false; } int main() { int cas = 1; int T; scanf("%d", &T); while(T--) { scanf("%d %d %d", &n, &m1, &m2); for(int i = 0; i < n; i++) scanf("%d", &a[i]); int l = 0; for(int i = 1; i < (1<<n); i++) { if(ok(i)) { b[l++] = i; dp[i] = 1; } else dp[i] = INF; } dp[0] = 0; // printf("%d\n", l); for(int s = 1; s < (1<<n); s++) { for(int i = s; i; i = (i-1)&s) { if(dp[i] == INF) continue; dp[s] = min(dp[s], dp[s^i]+dp[i]); } } printf("Scenario #%d:\n%d\n\n", cas++, dp[(1<<n)-1]); } return 0; }
POJ 2923 Relocation / 状态压缩DP,布布扣,bubuko.com
原文:http://blog.csdn.net/u011686226/article/details/21413345