首页 > 代码库 > hdu 4778 Gems Fight!
hdu 4778 Gems Fight!
第一次写状压dp……
题意:http://blog.csdn.net/dyx404514/article/details/15506601
状压dp+博弈吧……
#include<iostream> #include<map> #include<string> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<queue> #include<vector> #include<algorithm> using namespace std; int dp[2100000]; int bag[21][8]; int g,b,s; int dfs(int state,int *remain,int all) { int t[8]; int i,sum,j; if(state==0||all==0) return 0; if(dp[state]!=-1) return dp[state]; for(i=0;i<b;i++) { if((state>>i)&1) { sum=0; for(j=0;j<g;j++) { t[j]=bag[i][j]+remain[j]; sum+=t[j]/s; t[j]%=s; } if(sum) { if(dp[state]==-1) dp[state]=sum+dfs(state^(1<<i),t,all-sum); else dp[state]=max(dp[state],sum+dfs(state^(1<<i),t,all-sum)); } else { if(dp[state]==-1) dp[state]=all-dfs(state^(1<<i),t,all); else dp[state]=max(dp[state],all-dfs(state^(1<<i),t,all)); } } } return dp[state]; } int main() { int i,j,t,n,sum; int remain[8]; while(scanf("%d%d%d",&g,&b,&s)&&g||b||s) { memset(bag,0,sizeof(bag)); for(i=0;i<b;i++) { scanf("%d",&n); while(n--) { scanf("%d",&t); bag[i][t-1]++; } } sum=0; for(i=0;i<g;i++) { t=0; for(j=0;j<b;j++) t+=bag[j][i]; sum+=t/s; } memset(dp,-1,sizeof(dp)); memset(remain,0,sizeof(remain)); printf("%d\n",2*dfs((1<<b)-1,remain,sum)-sum); } return 0; }
hdu 4778 Gems Fight!
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。