本文共 1502 字，大约阅读时间需要 5 分钟。
/**题意：给你n个数去合并（这n个数只包含2,4,8,16），先挑选一些数得到这些数的和， 然后把这些数合并得到的值相加，使得最后的值最大。题解：状态压缩。我们可以把取得数放进队列使得队列的值按从大到小排序 能合并的尽量合并 （队列最多13个数）16 * 500 = 8000 < (1 << 13)注：这题要用到滚动数组（只用当前行和上一行 用1代表当前行 0代表上一行）**/#include #include #include #include #include using namespace std;#define maxn 1<<13#define M 550int dp[2][maxn];int b[M];int main(){// freopen("1.txt","r",stdin); int t,n; cin >> t; while(t --){ cin >> n; for(int i = 1;i <= n;i++) cin >> b[i]; memset(dp,-1,sizeof(dp)); dp[0][0] = 0 ; int cnt = 1 << 13 ; for(int i = 1;i <= n;i++){ for(int st = 0;st <= cnt;st++){ if(dp[(i-1)%2][st] != -1){ //不放 dp[i%2][st] = max(dp[i%2][st],dp[(i-1)%2][st]) ; int tmp = 0; if(st){ //找到队列的最小值 for(int j = 0;j <= 12;j ++){ if(st & (1< << j);break; } } } if(tmp > b[i])//如果tmp 大于当前这个数则加入队列 dp[i%2][st + b[i]] = max(dp[i%2][st + b[i]],dp[(i-1)%2][st] + b[i]); else if(tmp < b[i])//如果tmp小于当前这个数则加入队列并把前面的数全部清空 dp[i%2][b[i]] = max(dp[i%2][b[i]],dp[(i-1)%2][st] + b[i]); else {//如果tmp等于当前这个数，则合并 int S = st,sum = b[i] , res = b[i]; while(S&res){ sum += res * 2; S -= res; res <<= 1; } dp[i%2][res + S] = max(dp[i%2][res + S],dp[(i-1)%2][st] + sum); } } } } int ans = 0; for(int i = 0;i <= cnt;i++) ans = max(ans,dp[n%2][i]); cout << ans << endl; } return 0;}
转载地址：http://ecsgi.baihongyu.com/