hdu 2167 状态压缩
/*与1565的解法差不多*/
#include<stdio.h>
#include<string.h>
int map[16][16];
int dp[2][1<<16];
int h[1<<16];
int Max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int m,i,j,k,max;
m=0;
for(i=0;i<(1<<16);i++)
if((i&(i<<1))==0)
h[m++]=i;
char s[1001];
while(gets(s))
{
int len=strlen(s);
if(len==0)
break;
int num=0;
for(i=0;i<len;i+=3)
{
map[0][num++]=10*(s[i]-'0')+(s[i+1]-'0');
}
for(i=1;i<num;i++)
{
gets(s);
int k=0;
for(j=0;j<len;j+=3)
map[i][k++]=10*(s[j]-'0')+(s[j+1]-'0');
}
memset(dp,0,sizeof(dp));
int p=0;
for(i=0;i<num;i++)
{
p^=1;
for(j=0;j<m;j++)
{
if(h[j]>(1<<num))
break;
max=0;
for(k=0;k<num;k++)
if(h[j]&(1<<k))
max+=map[i][k];
for(k=0;k<m;k++)
{
if(h[k]>(1<<num))
break;
if(h[j]&h[k])
continue;
if(h[j]&(h[k]<<1))
continue;
if(h[j]&(h[k]>>1))
continue;
dp[p][h[j]]=Max(dp[p][h[j]],dp[1-p][h[k]]+max);
}
}
}
int max=0;
for(i=0;i<m&&i<=(1<<num);i++)
if(max<dp[p][h[i]])
max=dp[p][h[i]];
printf("%d\n",max);
getchar();
}
return 0;
}
最新文章
- centos 查看脚本
- Neil&#183;Zou 语录一
- D_S 线性表的顺序表示和实现
- Intellij编译时报“java: System Java Compiler was not found in classpath”
- C#多线程编程(转)
- 解决在sublime text3在ubuntu下无法输入中文的问题
- 简单理解Hibernate三种状态的概念及互相转化
- 最短路径算法之一——Floyd算法
- WifiDog系统
- bash变量
- Canvas画布实现自定义时钟效果
- (一)初识Redis
- Web版需求征集系统所得1,servlet中获取checkbox复选框的值
- 常用sql语句总结(二)(更新数据,序列,创建数据表,约束,注释)
- 安卓测试工具uiautomator无法打开失败报错解决方案
- nodejs操作 mongoose(mongodb)和Sequelize(mysql)查询数据后添加新属性未生效
- 安装cmake
- Logging常用handlers的使用
- 廖雪峰Java7处理日期和时间-4最佳实践-最佳实践
- 搭建yum服务器