首页 > 代码库 > 状态压缩dp zoj3802
状态压缩dp zoj3802
做这个题的时候看了看时间复杂度觉得应该是个贪心或者dp，然后贪心又很快被否定了，因为不具备贪心的一些特性，想了想觉得没什么思路。看了下网上的思路，真是让人拍案叫绝，算法的魅力就在于此啊。。
首先dp就意味着要寻找一些状态，我觉得500的状态太多了根本无从保存啊。网上的思路说难也不难，就是只保存下降的序列，因为能合并的只有下降的序列，上一个状态能够传递到下面的有不要当前，合并，当前值比递降序列最小的还小就归并，否则地将序列变成a[i];
我一下就明白了然后开始敲，TE！
各种优化
找能否合并由暴力找最小值变成j&(a[i]-1) TE
输入数所有除以2输出乘2这又减了一半时间复杂度 还是TE
气的我肝都疼了 看了看网上代码，用的滚动数组，哦。。。的确比我傻傻的用[500][8*500]少了250倍，改了改wa掉了我qu
于是我按照输入可能有一处理了一下ac！好开心~
代码如下
#include<iostream>#include<stdio.h>#include<string.h>using namespace std;const int maxa = 505;int dp[2][8*maxa];int a[maxa];int main(){ int t; //freopen("in.cpp", "r", stdin); int n; scanf("%d", &t); while(t--){ scanf("%d", &n); int sum = 0; for(int i = 1; i <= n ; i++){ scanf("%d", &a[i]); a[i]/=2; sum += a[i]; } memset(dp, -1, sizeof(dp)); dp[0][0] = 0; for(int g = 1; g <= n; g++){ int I = g%2; int II = (g+1)%2; for(int j = 0; j <= sum; j++){ if(dp[II][j]!=-1){ dp[I][j] = max(dp[I][j],dp[II][j]); if((a[g] -1)&j){ dp[I][a[g]] = max(dp[I][a[g]], dp[II][j]+a[g]); }else{ int mm = a[g]; int k = 0; int oo = a[g]; while(oo & j){ mm += oo*2; oo*=2; }//printf("%d %d\n", i, j, dp[i][]); dp[I][j+a[g]] = max(dp[I][j+a[g]], dp[II][j] + mm); } } } } int maxn = 0; for(int i = 0; i <= sum ;i++){ maxn = max(maxn, dp[(n)%2][i]); } printf("%d\n", 2*maxn); }}
状态压缩dp zoj3802
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。