传送门

第一道插头 $dp$

由于讲不清楚所以假装各位早就会插头 $dp$ 了

首先要的是一个闭合回路,所以可以用括号表示法表示状态,然后大力分类讨论

$1.$ 没有右插头和下插头

那么我们可以啥也不干,或者加一个右插头和下插头

$2.$ 只有下插头没有右插头

那么我们可以要把下插头继续延伸,可以向下或者向右

$3.$ 只有右插头没有下插头:

同理我们可以往下或者往右延伸

$4.$ 右插头和下插头都有:这个又要分情况讨论

  $a.$ 插头都是左括号,那么要把两个联通还要把右边原来匹配的右括号改成左括号

  

  $b.$ 插头都是右括号,那么要把两个联通还要把左边原本匹配的左括号改成右括号

  

  $c.$ 右插头是左括号,下插头是右括号,那么直接联通即可,不需要改变其他括号

  

  $d.$ 右插头是右括号,下插头是左括号,如果联通则一定形成一个闭合回路,那么如果其他地方没有插头则直接把当前状态计入答案,否则此状态不合法,不用延伸状态(右图是一种不合法状态)

  

然后根据考虑到的所有状态慢慢转移即可......

因为数据比较大所以用滚动数组和哈希表维护状态,状态在加入哈希表时更新

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline int read()
{
int x=,f=; char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }
return x*f;
}
const int N=3e5;
const ll INF=1e18;
int n,m,a[][],bit[],cur,pre;
ll f[][N+],Ans=-INF;
int fir[N+],from[N+],to[][N+],cntt[];//哈希表
inline void insert(int sta,ll val)//插入状态并更新f
{
int p=sta%N;
for(int i=fir[p];i;i=from[i])
{
if(to[cur][i]!=sta) continue;
f[cur][i]=max(f[cur][i],val); return;
}
from[++cntt[cur]]=fir[p]; fir[p]=cntt[cur];
to[cur][cntt[cur]]=sta; f[cur][cntt[cur]]=val;
}
void DP()
{
cntt[cur]=; int now,down,right; ll val;
for(int i=;i<=n;i++)//枚举行
{
for(int j=;j<=cntt[cur];j++) to[cur][j]<<=;//每一行末尾,状态统一左移四进制下的一位
for(int j=;j<=m;j++)//枚举列
{
pre=cur; cur^=; cntt[cur]=; memset(fir,,sizeof(fir));//清空哈希表
for(int k=;k<=cntt[pre];k++)//枚举上一行的状态
{
now=to[pre][k]; val=f[pre][k];
right=(now>>bit[j-])%; down=(now>>bit[j])%;//提出插头状态
if(!down&&!right)//没有插头
{
insert(now,val);//继续没有插头
if(j!=m) insert(now+(<<bit[j-])+((<<bit[j])<<),val+a[i][j]);//多一个右插头和下插头
}
if(down&&!right)//只有下插头
{
insert(now-down*(<<bit[j])+down*(<<bit[j-]),val+a[i][j]);//向下延伸
if(j!=m) insert(now,val+a[i][j]);//向右延伸
}
if(!down&&right)//只有右插头
{
insert(now,val+a[i][j]);//向下延伸
if(j!=m) insert(now-right*(<<bit[j-])+right*(<<bit[j]),val+a[i][j]);//向右延伸
}
if(down==&&right==)//插头为'(('
{
int cnt=;
for(int l=j+;l<=m;l++)//找到右边第一个和当前下插头匹配的')'
{
if((now>>bit[l])%==) cnt++;
if((now>>bit[l])%==) cnt--;
if(!cnt)
{
insert(now-(<<bit[l])-(<<bit[j-])-(<<bit[j]),val+a[i][j]);//联通并改')'为'('
break;
}
}
}
if(down==&&right==)//插头为'))'
{
int cnt=;
for(int l=j-;l>=;l--)//找到左边第一个和当前右插头匹配的'('
{
if((now>>bit[l])%==) cnt--;
if((now>>bit[l])%==) cnt++;
if(!cnt)
{
insert(now+(<<bit[l])-((<<bit[j-])<<)-((<<bit[j])<<),val+a[i][j]);//联通并改'('为')'
break;
}
}
}
if(down==&&right==)//')('
insert(now-((<<bit[j-])<<)-(<<bit[j]),val+a[i][j]);//直接联通即可
if(down==&&right==)//'()'
if(now==((<<bit[j])<<)+(<<bit[j-]))//当前状态只有这两个插头
Ans=max(Ans,val+a[i][j]);//统计答案
}
}
}
}
int main()
{
n=read(),m=read();
for(int i=;i<=;i++) bit[i]=(i<<);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++) a[i][j]=read();
DP();
printf("%lld\n",Ans);
return ;
}

最新文章

  1. JSON资料整理
  2. eclipse创建maven管理Spark的scala
  3. Sharepoint学习笔记—习题系列--70-576习题解析 -(Q81-Q83)
  4. 《Kotli&#173;n for &#173;androi&#173;d Deve&#173;lopers&#173;》中文翻译
  5. PL/SQL查询Oracle数据乱码/Oracle客户端乱码解决办法
  6. 关于H5+css3的一些简单知识
  7. 在iframe里调用parent.func()引出的js函数运行在它们被定义的作用域里,而不是它们被执行的作用域里
  8. spring配置文件中id与name
  9. 再说JNDI
  10. erlang四种监控策略
  11. java利用“映射文件访问”(MapperByteBuffer)处理文件与单纯利用Buffer来处理文件的快慢比较
  12. oracle开启一个用户
  13. linux dialog详解(图形化shell)
  14. 一、PHP概述 - PHP零基础快速入门
  15. 【XSY2962】作业 数学
  16. 逃逸分析(Escape Analysis)
  17. Vue+koa2开发一款全栈小程序(3.vue入门、Mpvue入门)
  18. AngularJS之拖拽排序(ngDraggable.js)
  19. C语言定义的操作mysql数据库的接口
  20. PAT A1136 A Delayed Palindrome (20 分)——回文,大整数

热门文章

  1. Email 发送
  2. NOIP2018 D1T3赛道修建
  3. luogu P1077 摆花 x
  4. IoC容器简介
  5. Vue.js 使用 Font Awesome 小图标
  6. Comparable接口与Comparator接口的比较————Comparator接口详解
  7. webrtc相关概念
  8. jQuery中的闭包和js中的闭包总结
  9. Jmeter 设置连接oracle数据库
  10. 七、SpringBoot项目集成JSP以及项目不同启动方式及访问路径配置