http://www.lydsy.com/JudgeOnline/problem.php?id=1187 (题目链接)

题意

  一个$n*m$的矩阵,其中每一个位置有一个权值,求一条回路使得经过的位置的权值和最大。

Solution

  插头dp,插头维护连通信息,更新答案的条件就是合并的左插头和右插头属于同一连通块,且当前状态已经没有其它插头了。更新完答案后这个状态不会再被记入下一次dp。

代码

// bzoj1185
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define HAS 6311
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxd=10,maxs=100010,maxh=6400;
int code[maxd],cnts[maxd],n,m;
int head[maxh],next[maxs];
int size[2],tot[2][maxs],s[2][maxs]; void decode(int st) {
for (int i=m;i>=0;i--) code[i]=st&7,st>>=3;
}
int encode() {
int st=0,cnt=0;
memset(cnts,-1,sizeof(cnts));cnts[0]=0;
for (int i=0;i<=m;i++) {
if (cnts[code[i]]==-1) cnts[code[i]]=++cnt;
code[i]=cnts[code[i]];
}
for (int i=0;i<=m;i++) st=st<<3|code[i];
return st;
}
void shift() {
for (int i=m;i;i--) code[i]=code[i-1];code[0]=0;
}
void add(int p,int num) {
int st=encode();
int id=st%HAS;
for (int i=head[id];i;i=next[i])
if (s[p][i]==st) {tot[p][i]=max(tot[p][i],num);return;}
s[p][++size[p]]=st;tot[p][size[p]]=num;
next[size[p]]=head[id];head[id]=size[p];
}
int main() {
scanf("%d%d",&n,&m);
int p=0,ans=-inf,val;
size[0]=1;tot[0][1]=0;s[0][1]=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++) {
scanf("%d",&val);
size[p^=1]=0;
memset(head,0,sizeof(head));
for (int k=1;k<=size[p^1];k++) {
decode(s[p^1][k]);
int left=code[j-1],up=code[j];
if (left && up) {
if (left==up) {
int flag=0;
for (int l=0;l<j-1;l++) if (code[l]) {flag=1;break;}
for (int l=j+1;l<=m;l++) if (code[l]) {flag=1;break;}
if (!flag) ans=max(ans,tot[p^1][k]+val);
}
else {
code[j-1]=code[j]=0;
for (int l=0;l<=m;l++) if (code[l]==up) code[l]=left;
if (j==m) shift();
add(p,tot[p^1][k]+val);
}
}
else if (left || up) {
int tmp=left ? left : up;
if (j<m) {
code[j-1]=0,code[j]=tmp;
add(p,tot[p^1][k]+val);
}
if (i<n) {
code[j-1]=tmp,code[j]=0;
if (j==m) shift();
add(p,tot[p^1][k]+val);
}
}
else {
if (i<n && j<m) {
code[j-1]=code[j]=8;
add(p,tot[p^1][k]+val);
}
code[j-1]=code[j]=0;
if (j==m) shift();
add(p,tot[p^1][k]);
}
}
}
printf("%d",ans);
return 0;
}

最新文章

  1. C++基础知识(5)---类和对象
  2. Win10 VC++6 无法启动此程序,因为计算机中丢失mfc42d.dll 需要提升
  3. mac常用的命令
  4. 直接拿来用!最火的Android开源项目(完结篇)(转)
  5. &quot;ORA-12154: TNS:could not resolve the connect identifier specified&quot;的解决办法
  6. Solr4.8.0源码分析(27)之ImplicitDocRouter和CompositeIdRouter
  7. CXF处理Date类型的俩种方式
  8. linux 文件查找和压缩工具
  9. jQuery插件jqplot的详细配置说明和渲染器
  10. UVA 12166 Equilibrium Mobile
  11. Customizing Zend Studio Using the Welcome Page
  12. VS2010/MFC设置对话框控件的Tab顺序
  13. Liunx的DHCP配置
  14. 【Jquery系列】详解Jquery对象和Dom对象
  15. http://zaojiasys.jianshe99.com 建造师数据泄漏,可以查看全部所有人的信息!
  16. shiro--认证部分
  17. 【转】Win32程序中调用ActiveX控件
  18. mybatis学习 十三 resultMap标签 一对一
  19. Codeforces Round #264 (Div. 2) C. Gargari and Bishops 主教攻击
  20. gpexpand分析

热门文章

  1. RobotFramework测试环境搭建记录
  2. 微服务构建: Spring Boot
  3. Netty源码分析第3章(客户端接入流程)----&gt;第2节: 处理接入事件之handle的创建
  4. [Hanani]高数相关知识记录
  5. maven 添加spring/springmvc依赖项
  6. Homebrew1.5之后安装PHP和扩展
  7. python下graphviz安装
  8. “吃神么,买神么”的第二个Sprint计划
  9. C#简单窗体应用程序(三)
  10. Socket 记录