首先,最朴素的思想为暴搜所有解o(2^n)不可接受;
已d[ i ] [ j ] 代表前 i 个数字 里 已作出选择后产生的序列记为 j ,j 最大为 (16,8,4,2全部除以压缩一下) 4000; 注意 j 保存的是一个序列经产生所属运算后最后的递减数数列; 举个栗子 : 14(8 4 2) 当添入 2 变为 16, 添入 4 变为 4 ,填入1变为 15;
这样状态总数约二百万,加上剪枝(当j > sum(i)(sum(i) 为前 i 个宝藏的和) 可剪枝 ),已经足够快;
这样 i 的状态依赖有 i - 1可转移至它 的状态;可使用刷表法;
#include <cstdio> #include <cstring> #include <iostream> #include <cmath> using namespace std; const int maxn = 505; const int maxm = 4010; int a[maxn],n,d[maxn][maxm],sum[maxn]; int getnum(int s,int& s0){ if(s==0) { return 0; } int temp = log2(s0); int res=0; for(int i=0;i<=12;i++) { if((s>>i)&1){ if(i==temp){ res+=(1<<(temp+1)); temp+=1; s = s&(~(1<<i)); } else if(i > temp){ s0 = s | (1<<temp); return res; } else return 0; } } s0 = 1<<temp; return res; } int main() { int T; scanf("%d",&T); while(T--){ scanf("%d",&n); sum[0]=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); a[i]/=2; sum[i]=sum[i-1]+a[i]; } for(int i=0;i<=n;i++) for(int j=0;j<maxm;j++){ if(j>sum[i]) break; d[i][j]=-1; } d[0][0]=0; for(int i=0;i<n;i++) for(int j=0;j<maxm;j++){ if(j > sum[i]) break; if(d[i][j]==-1) continue; d[i+1][j]=max(d[i+1][j],d[i][j]); int tt = a[i+1]; int fen = getnum(j,tt); d[i+1][tt] = max(d[i+1][tt],d[i][j]+a[i+1]+fen); } int res=0; for(int i=0;i<maxm;i++){ if(i > sum[n]) break; res=max(res,d[n][i]); } printf("%d\n",res*2); } return 0; }