hdu 2167(状压dp)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2167

思路:经典的状压dp题,前后,上下,对角8个位置不能取,状态压缩枚举即可所有情况,递推关系是为dp[i][j]=max(dp[i][j],dp[i-1][k]+sum[i][j]),具体的含义见code:

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int s[<<];
int sum[][<<];
int dp[][<<];
int map[][];
int n,m,ans; void Solve()
{
m=;
for(int i=;i<(<<n);i++){
if((i&(i<<))==)s[m++]=i;//所有合法的状态
}
memset(sum,,sizeof(sum));
memset(dp,,sizeof(dp));
for(int i=;i<n;i++){
for(int j=;j<m;j++){
for(int k=;k<n;k++){
if(s[j]&(<<k))sum[i][j]+=map[i][k];//sum又来保存每一行的合法状态下的所有数的和
}
}
}
for(int i=;i<m;i++)dp[][i]=sum[][i];
for(int i=;i<n;i++){
for(int j=;j<m;j++){
for(int k=;k<m;k++){ //上一行状态
if(s[j]&s[k])continue;
if(s[j]&(s[k]>>))continue;
if(s[j]&(s[k]<<))continue;
dp[i][j]=max(dp[i][j],dp[i-][k]+sum[i][j]);
}
}
}
ans=;
for(int i=;i<m;i++){
ans=max(ans,dp[n-][i]);
}
printf("%d\n",ans);
} int main()
{
char str[];
while(gets(str)){
int len=strlen(str);
n=;
for(int i=;i<len;i+=){
map[][n++]=(str[i]-'')*+(str[i+]-'');
}
for(int i=;i<n;i++){
int nn=;
gets(str);
for(int j=;j<len;j+=){
map[i][nn++]=(str[j]-'')*+(str[j+]-'');
}
}
Solve();
getchar();
}
return ;
}
上一篇:Html5用Canvas制作画图板


下一篇:Travel(HDU 4284状压dp)