《挑战程序设计竞赛》上DP的一道习题。
很裸的多重背包。下面对比一下方法，倍增，优化定义，单调队列。
一开始我写的倍增，把C[i]分解成小于C[i]的2^x和一个余数r。
dp[i][j]的定义前i个数字能否到凑出j来，改成一位滚动数组。
#include<cstdio> #include<iostream> #include<string> #include<cstring> #include<queue> #include<vector> #include<stack> #include<vector> #include<map> #include<set> #include<algorithm> //#include<bits/stdc++.h> using namespace std; #define PS push #define PB push_back #define MP make_pair #define fi first #define se second const int maxm = 1e5+5; const int maxn = 101; bool dp[maxm]; int A[maxn], C[maxn]; int n, m; inline int read() { int ret; char c; while(c = getchar(),c<'0'||c>'9'); ret = c-'0'; while(c = getchar(),c>='0'&&c<='9') ret = ret*10 + c-'0'; return ret; } //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif dp[0] = true; while(scanf("%d%d",&n,&m),n+m){ for(int i = 0; i < n; i++) A[i] = read(); for(int i = 0; i < n; i++){ C[i] = read(); } memset(dp+1,0,sizeof(bool)*m); for(int i = 0; i < n; i++){ int b = 1,vol = A[i]; while((1<<b)<=C[i]+1){ //11...111 (b) <= C[i] -> 100.... <= C[i]+1 for(int S = m; S >= vol; S--){ dp[S] = dp[S-vol]||dp[S]; } b++; vol<<=1; } int r = C[i]-(1<<(b-1))+1; if(r){ int Vol = A[i]*r; for(int S = m; S >= Vol; S--){ dp[S] = dp[S-Vol]||dp[S]; } } } int ans = 0; for(int i = 1; i <= m; i++) ans += dp[i]; printf("%d ",ans); } return 0; }
复杂度是O(n*m*sigma(logC[i]))。然后果断就TLE了。
再优化只有单调队列了，扎扎并没有想到怎么用单调队列。
书上的解法是优化定义，同样的时间复杂度记录bool信息太浪费了。
dp[i][j]表示前i种凑出面值j时第i种硬币最多的剩余。
核心代码：
int ans = 0; memset(dp+1,-1,sizeof(int)*m); for(int i = 0; i < n; i++){ for(int j = 0; j <= m; j++){ if(~dp[j]) dp[j] = C[i]; //之前凑出了j else if(j >= A[i] && dp[j-A[i]]>0) { //还可以在凑 dp[j] = dp[j-A[i]] - 1; ans++; }else dp[j] = -1; //凑不出 } }
跑了1985ms。
另外还发现一件有意思的事情，
当我用一个临时变量数组cnt[j]记录凑出j的最小次数的时候，跑了1235ms。（系统分配似乎更快一点？
int ans = 0; memset(dp+1,0,sizeof(bool)*m); for(int i = 0; i < n; i++){ int cnt[maxm] = {}; for(int j = A[i]; j <= m; j++){ if(!dp[j] && dp[j-A[i]] && cnt[j-A[i]] < C[i]){ cnt[j] = cnt[j-A[i]] + 1; ans++; dp[j] = true; } } }
参考了http://www.cnblogs.com/xinsheng/archive/2013/12/04/3458362.html之后，明白了单调队列的做法的。
总体来说是划分同余类，对于一个同余类用单调队列维护滑动窗口的最小值。（左端为最多减去C[i]个物品的的状态
这道题只要判断存在性，连单调性都用不上(insert不需要删除队尾元素)，只要维护滑动窗口的和以及大小就可以了。
但是这道题数据丧心病狂，直接分组常数比较大TLE了。我改成判断0-1和完全才2891 ms飘过（常数写丑了
int ans = 0; memset(dp+1,0,sizeof(bool)*m); for(int i = 0; i < n; i++){ if(C[i] == 1){ for(int j = m; j >= A[i]; j--){ dp[j] = dp[j-A[i]] || dp[j]; } } else if(A[i]*C[i] >= m){ for(int j = A[i]; j <= m; j++){ dp[j] = dp[j-A[i]] || dp[j]; } } else { for(int r = 0; r < A[i]; r++){ int sum = 0, hd = 0, rr = 0; for(int j = r; j <= m; j += A[i]){ if(rr - hd > C[i]){ sum -= q[hd++]; } sum += q[rr++] = dp[j]; if(sum) dp[j] = true; } } } } for(int i = 1; i <= m; i++) ans += dp[i];
似乎完全的情况比较多的情况，我只改了一个语句的不同结果。。
dp[j] = dp[j-A[i]] || dp[j]; 2891 ms
if(dp[j-A[i]]) dp[j] = true; 2813 ms
if(dp[j-A[i]] && !dp[j]) dp[j] = true; 2110 ms