二进制优化。。单调队列的不会用。。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <string> #include <queue> #include <stack> #include <map> using namespace std; typedef long long ll; int const MAXN = 100100; int n[6],f[MAXN],v[MAXN],w[MAXN]; inline int Min(int a,int b){ return a<b?a:b; } inline int Max(int a,int b){ return a>b?a:b; } inline void Init(){ for(int i = 0;i < MAXN;i++){ f[i] = 0; } } int main(){ int k = 1; while(~scanf("%d%d%d%d%d%d",&n[0],&n[1],&n[2],&n[3],&n[4],&n[5])){ int s = 6 * n[5] + 5 * n[4] + 4 * n[3] + 3 * n[2] + 2 * n[1] + n[0]; if(!s)break; printf("Collection #%d:\n",k++); int cnt = 0; for(int i = 0;i < 6;i++){ for(int j = 1;j <= n[i];j <<=1){ v[cnt] = j * (i + 1); w[cnt++] = j * (i + 1); n[i] -= j; } if(n[i] > 0){ v[cnt] = n[i] * (i + 1); w[cnt++] = n[i] * (i + 1); } } int s1 = s>>1; Init(); for(int i = 0;i < cnt;i++){ for(int j = s1;j >= w[i];j--){ f[j] = Max(f[j],f[j - w[i]] + v[i]); } } int s2 = s - f[s1]; if(s2 == s1) printf("Can be divided.\n\n"); else printf("Can't be divided.\n\n"); } return 0; } /* 1 0 1 2 0 0 1 0 0 0 1 1 0 0 0 0 0 0 */