首页 > 代码库 > hdu 4778 Gems Fight!(状态压缩DP)
hdu 4778 Gems Fight!(状态压缩DP)
又是一道状态压缩,刚开始老是往博弈的方法想,总是没思路。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=21;const int inf=0x3f3f3f3f;int g,n,s;int sum[1<<N];int res[10];int c[22][10];int dp[1<<N];int main(){// freopen("in","r",stdin); while(scanf("%d%d%d",&g,&n,&s),g|n|s){ memset(c,0,sizeof c); for(int i=0;i<n;i++){ int k,x; scanf("%d",&k); while(k--){ scanf("%d",&x); c[i][x-1]++; } } int all=1<<n; for(int i=0;i<all;i++){ sum[i]=0; memset(res,0,sizeof res); for(int j=0;j<n;j++){ if(i&(1<<j)){ for(int k=0;k<g;k++)res[k]+=c[j][k]; } } for(int j=0;j<g;j++)sum[i]+=res[j]/s; } dp[0]=0; for(int i=1;i<all;i++){ dp[i]=-inf; for(int j=0;j<n;j++){ if(i&(1<<j)){ int pre=i^(1<<j); int now=(all-1)^pre; int tmp=sum[now]-sum[now^(1<<j)]; if(tmp)dp[i]=max(dp[i],dp[pre]+tmp); else dp[i]=max(dp[i],-dp[pre]); } } } printf("%d\n",dp[all-1]); } return 0;}
hdu 4778 Gems Fight!(状态压缩DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。