正文

[hdu2167]Pebbles

IP云
IP云V管理员/2 阅读
09/21
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

来自FallDream的博客，未经允许，请勿转载，谢谢。

给定一个方阵，你要取出一些数字，满足没有两个格子八联通相邻的前提下和最大，求这个和

n<=15

插头dp，保存轮廓线以及目前转移点左上方那个格子的状态，枚举格子转移即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#define MN 15
using namespace std;
inline int read()
{
int x = , f = ; char ch = getchar();
while(ch < '' || ch > ''){ if(ch == '-') f = -; ch = getchar();}
while(ch >= '' && ch <= ''){x = x * + ch - '';ch = getchar();}
return x * f;
}char st[];
int a[MN+][MN+],m,f[][<<];int Strread()
{
int top=,j=;
for(int i=;st[i]==' '||(st[i]>=''&&st[i]<='');++i)
if(st[i]==' ') a[][++top]=j,j=;
else j=j*+st[i]-'';
return a[][++top]=j,top;
}
inline void R(int&x,int y){y>x?x=y:;}
int main()
{
while(cin.getline(st,))
{
m=Strread();if(m==&&a[][]==) continue;
for(int i=;i<=m;++i)
for(int j=;j<=m;++j)
a[i][j]=read();
memset(f,,sizeof(f));
int now=,pre=;
for(int i=;i<=m;++i)
for(int j=;j<=m;++j,swap(now,pre),memset(f[now],,sizeof(f[now])))
for(int k=;k<<<(m+);++k)
{
R(f[now][(k&((<<m)-(<<(j-))-))|((k&(<<(j-)))?(<<m):)],f[pre][k]);
if((j==||(!((k&(<<m)))&&!(k&(<<(j-)))))&&!(k&(<<(j-)))&&(j==m||!(k&(<<j))))
R(f[now][(k&((<<m)-))|(<<(j-))|((k&(<<(j-)))?(<<m):)],f[pre][k]+a[i][j]);
}
int ans=;
for(int i=;i<<<(m+);++i) ans=max(ans,f[pre][i]);
cout<<ans<<endl;
}
return ;
}