首页 > 代码库 > Hdu-1565 方格取数(1) (状态压缩dp入门题
Hdu-1565 方格取数(1) (状态压缩dp入门题
方格取数(1)
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4702 Accepted Submission(s): 1782
Problem Description
给你一个n*n的格子的棋盘,每个格子里面有一个非负数。
从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取的数所在的2个格子不能相邻,并且取出的数的和最大。
从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取的数所在的2个格子不能相邻,并且取出的数的和最大。
Input
包括多个测试实例,每个测试实例包括一个整数n 和n*n个非负数(n<=20)
Output
对于每个测试实例,输出可能取得的最大的和
Sample Input
3 75 15 21 75 15 28 34 70 5
Sample Output
188
Poj - 3254 Corn Fields
类似。用dp[i][j]表示前i行,第i行选第j种状态时的最优解,
首先找出所有本行不冲突的状态(即这一行中没有相邻的情况),存入state数组
计算出第i行取第j种状态时可得到的数值stn[i][j]
那么dp[i][j]=max{dp[i][j],dp[i-1][k]+stn[i][j]}(k表示第i-1行取第k种状态
最终答案即为dp[n][j]中的最大值。
代码:
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int hpn=18000; int state[hpn],stn[25][hpn],dp[25][hpn]; //dp[i][j]:前i行,第i行选第j种状态时的最优解 int mst,map[25][25];//第i行选第j种状态时的值 inline int bet(int x,int y) { if(x>y) return x; return y; } void find_all_state(int n) { memset(state,0,sizeof(state)); mst=0;//最多有多少种状态 int lin=(1<<n),index=1; for(int i=0;i<lin;++i) { if((i&(i<<1))==0) { state[index]=i; ++mst; ++index; } } } int main() { int n; while(cin>>n) { if(n==0) { cout<<0<<endl; continue; } find_all_state(n); for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) { scanf("%d",&map[i][j]); } } memset(stn,0,sizeof(stn)); for(int i=1;i<=n;++i) { for(int j=1;j<=mst;++j) { int b=n; for(int t=1;t<(1<<n);t=(t<<1)) { if((t&state[j])!=0) { stn[i][j]+=map[i][b]; } --b; } } }//统计第i行选第j种状态时可得到的值 memset(dp,0,sizeof(dp)); for(int i=1;i<=mst;++i)//第一行取第i种状态时 { dp[1][i]=stn[1][i]; } for(int i=2;i<=n;++i)//对于第i行 { for(int j=1;j<=mst;++j)//取第j种状态 { for(int k=1;k<=mst;++k)//第i-1行取第k种状态 { if((state[j]&state[k])!=0) continue; dp[i][j]=bet(dp[i][j],dp[i-1][k]+stn[i][j]); } } } int ans=0; for(int i=1;i<=mst;++i) { ans=bet(ans,dp[n][i]); } cout<<ans<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。