hdu2167 方格取数 状态压缩dp
题意:
方格取数,八个方向的限制。
思路:
八个方向的不能用最大流了,四个的可以,八个的不能抽象成二分图,所以目测只能用dp来跑,dp[i][j]表示的是第i行j状态的最优,具体看代码。
#include<stdio.h>
#include<string.h>
int dp[16][1<<15];
int map[16][16];
int zt[1<<15];
int maxx(int x ,int y)
{
return x > y ? x : y;
}
int DP(int n)
{
int mk = 0;
for(int i = 0 ;i < (1<<n) ;i ++)
if((i & (i << 1)) == 0 ) zt[++mk] = i;
memset(dp ,0 ,sizeof(dp));
for(int i = 1 ;i <= n ;i ++)
for(int j = 1 ;j <= mk ;j ++)
{
int sum = 0;
for(int k = 1 ;k <= n ;k ++)
if(zt[j] & (1 << (k - 1))) sum += map[i][k];
dp[i][j] = sum;
for(int k = 1 ;k <= mk ;k ++)
{
if(zt[j] & zt[k]) continue;
if(zt[j] & zt[k]<<1) continue;
if(zt[j] & zt[k]>>1) continue;
dp[i][j] = maxx(dp[i][j] ,dp[i-1][k] + sum);
}
}
int Ans = 0;
for(int i = 1 ;i <= mk ;i ++)
Ans = maxx(Ans ,dp[n][i]);
return Ans;
}
int main ()
{
int n ,i ,j ,nowid;
while(~scanf("%d" ,&map[1][1]))
{
nowid = 1;
while(1)
{
scanf("%d" ,&map[1][++nowid]);
if(getchar() == '\n') break;
}
n = nowid;
for(i = 2 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
scanf("%d" ,&map[i][j]);
printf("%d\n" ,DP(n));
}
return 0;
}
相关文章
- DDR3命令状态(二)
- [SVN(ubuntu)] svn 文件状态标记含义
- 第三章 线程状态
- Oracle数据库使用出现错误-状态: 失败 ORA-01034: ORACLE not available ORA-27101: shared memory realm does not exist
- jquery判断checkbox是否选中及改变checkbox状态
- Java实现第八届蓝桥杯魔方状态
- HDU 1429 胜利大逃亡(续)(DP + 状态压缩)
- HDU 4628 Pieces(DP + 状态压缩)
- MFC Windows 程序设计[225]之滑动状态条联动(附源码)
- 使用jstack检测Java应用的死锁(deadlock)状态
- Atitit. 有限状态机 fsm 状态模式
- ios在release状态下不打印信息
- Android 以太网(有线网络)开关和状态的判断
- 单元格中输入数据时,QTextEdit如何直接进入编辑状态
- HDU 3001 Travelling (三进制状态压缩 DP)
- OSPF状态切换以及包内容的交互,以及如何根据LSDB还原单区域拓扑
- IPv6邻居状态监测
- Linux基础命令-stat显示文件的状态信息
- UVA 1508 - Equipment 状态压缩 枚举子集 dfs
- 【状态估计】带观测滞后多传感器系统的改进协方差交叉融合Kalman滤波器(Matlab代码实现)