注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 2167 Pebbles  

2014-03-29 11:27:21|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=2167
给出n*n的矩阵,每个单元格上一个数,现从矩阵里取数,使得相加和最大,如果一个数被取了,则周围8个方向的数都不能取。3<=n<=15。
典型的状态压缩dp,首先筛选出每一行所有可行状态,最多状态数为1579,当n等于15时。
因为只和上一层状态相关,所以只需要记录当前行的状态,判断相邻两行是否符合条件,巧用位运算来处理。

int n,c[16][16];
int f[16][1600]; //f[i][j]:第i行前j种状态的最优解
int num[16][1600]; //num[i][j]:第i行第j种状态下可取数之和
int pnum[16],pz[16][1600];
//pnum[i]:i*i的矩阵下的可行状态数,最多有1597种状态,当i等于15时候
//pz[i][j]:i*i的矩阵下的第j种可行状态

int jud(int a,int tmp) //判断a状态是否可行
{
if(a == 0)
return 1;
int p=a%2;
if(p == 1 && tmp == 1)
return 0;
return jud(a/2,p);
}

void init1() //打表所有矩阵(n从3到15),每一行的所有可行状态
{
for(int t=3;t<=15;t++)
{
int tot=1<<t;
pnum[t]=0;
for(int i=0;i<tot;i++)
{
if(!jud(i,0))
continue;
pz[t][pnum[t]++]=i;
}
}
}

int deal(int h,int a) //计算第h行,a状态下可取数之和
{
int t=0,r=0;
while(a)
{
if(a&1)
r+=c[h][t];
a>>=1;t++;
}
return r;
}

void init2() //打表每一行下,每种状态的可取数之和
{
for(int i=0;i<n;i++)
for(int j=0;j<pnum[n];j++)
num[i][j]=deal(i,pz[n][j]);
}

int jud2(int j,int k) //判断相邻两行,两种状态是否有冲突(巧用位运算)
{
if(j & k || (j>>1) & k || (j<<1) & k)
return 0;
return 1;
}

void solve()
{
MEM(f);MEM(num);
init2();
for(int i=0;i<n;i++)
{
for(int j=0;j<pnum[n];j++) //当前状态
{
if(i == 0) //如果是第一行,则不用看上一行
{
f[0][j]=num[0][j];
continue;
}
for(int k=0;k<pnum[n];k++) //前一行状态
{
if(!jud2(pz[n][j],pz[n][k]))
continue;
f[i][j]=max(f[i][j],f[i-1][k]+num[i][j]);
}
}
}
int ans=0;
for(int i=0;i<pnum[n];i++)
ans=max(ans,f[n-1][i]);
pf(ans);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
init1();
char s;
while(sf(c[0][0])!=EOF)
{
n=1;
s=getchar();
while(s != '\n')
{
sf(c[0][n++]);
s=getchar();
}
for(int i=1;i<n;i++)
for(int j=0;j<n;j++)
sf(c[i][j]);
solve();
}
return 0;
}


  评论这张
 
阅读(78)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017