正方形格通路(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
入门压缩dp，与
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;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。