题解 P3886 【[JLOI2009]神秘的生物】
GNAQ
2018-07-16 08:39:26
本文首发于博客 [FancyDreams' Blog](https://fancydreams.ink)
此题是一道经典的插头DP问题，如果没有接触过插头DP的有关内容，欢迎垂读：
### [博客专题“头插DP指北”](https://fancydreams.ink/2018/06/20/%E5%A4%B4%E6%8F%92dp%E6%8C%87%E5%8C%97/)
首先说明的是这份代码参考自 `vawait` 大佬 (肽聚了，写了无数插头DP……)
这道题还有一个很有意思的背景：
本题也就是Topcoder SRM312 CheapestIsland （by Petr）
仔细想想你会发现SRM312好像是06年的比赛……
**JLOI居然搬原题，差评 （不过也有可能是撞题了……）**
一种策略就是我们可以只转移有左插和上插的格子。可惜其实这是很不对的一个策略，你没法应付像这样：
真令人头秃。那怎么办呢?
-------
### 一些注意事项
首先你会发现，因为四个插头都是本质相同的，所以我们大可以用一个插头去概括它，也就是说，本题所谓的轮廓线是这样的：
也就是我们只需要保存 $n$ 个格子的最小表示就可以转移了。稍加分析可以得到我们需要八进制来表示这么多格子的最小表示。
--------
### 转移状态
按照一贯的套路我们又要讨论如何转移状态。基于对联通信息的维护，我们会有：
1. 当前格无插头
2. 当前格有插头
- 当前格属于“新建一个联通分量”
- 当前格加入之前的联通分量
所以一共有三种转移。
1非常好做。去掉即可。
2.1 非常好做，我们可以用 $7$ 来表示新建的联通分量
2.2 从`vawait`大佬那里看到了一个实现上的技巧, 就是让当前格的最小表示等于 $\mathrm{max(Dplug,Rplug)}$ 。然后让所有最小表示为 $\mathrm{min(Dplug,Rplug)}$ 的格子也等于它。
-------
### 判定状态合法性
这个题和之前的不一样，因为答案并不是最后更新，转移完之后状态也都不一定是合法的。
所以hash之前应该先判一下状态的合法性
1如果没有下插，或者下插（也就是当前格的上面一格）与轮廓线上其他格联通，那这样转移是合法的，反之一定不合法。
2.1和2.2是一定合法的。
----
### 更新答案
hash之前要重新编码，编码完之后如果当前轮廓线上有一个或零个联通分量都是满足题目要求的状态，可以更新答案。
--------
### hash
还是和上题Formula1一样。[(博客专题“头插DP指北”)](https://fancydreams.ink/2018/06/20/%E5%A4%B4%E6%8F%92dp%E6%8C%87%E5%8C%97/)不过我从vawait的代码里get到一个卡空间的技巧，就是把dp状态也压进hash表里。感觉也不难写。
-----------
### 重新编码
思路还是挺简单的。唯一需要合并联通分量的地方(2.2)也已经提前处理好了。直接看代码就能明白.
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<vector>
#define ll long long
#define mo 30007
#define mp make_pair
using namespace std;
int valx[13][13]={0};
int n=0; ll all_ans=-2*1e9;
int bits[10]={0},s[20]={0};
struct hash_table
{
int pre,state,dp;
}idx[2][1001000]={0};
int ptr[2][30010]={0},tots[2],pre=1,cnt=0;
inline void readx(int& x)
{
x=0; int k=1; register char ch=0;
while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
x*=k;
}
inline void reads()
{
readx(n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++) readx(valx[i][j]);
}
inline void init_bits() { for (int i=1;i<=10;i++) bits[i]=i*3; }
inline int hah(int sta,int val)
{
register int key=sta%mo;
for (int prex=ptr[cnt][key];prex;prex=idx[cnt][prex].pre) if (idx[cnt][prex].state==sta)
return idx[cnt][prex].dp=max(idx[cnt][prex].dp,val);
idx[cnt][++tots[cnt]].pre=ptr[cnt][key];
ptr[cnt][key]=tots[cnt];
idx[cnt][tots[cnt]].dp=val;
idx[cnt][tots[cnt]].state=sta;
return val;
}
inline void get_state(int sta)
{
for (int i=1;i<=n;i++) s[i]=(sta>>bits[i])&7;
s[0]=0;
}
inline int relabel(int val)
{
int t[20]; memset(t,0,sizeof t); int ctr1=0,sta=0;
for (int i=1;i<=n;i++) if (s[i])
{
if (t[s[i]]) s[i]=t[s[i]];
else s[i]=t[s[i]]=++ctr1;
}
for (int i=1;i<=n;i++) sta+=(s[i]<<bits[i]);
if (ctr1 && ctr1<=1) all_ans=max(all_ans,(ll)val);
return sta;
}
inline void DP()
{
register int r_plug,d_plug,nowans,cac1;
tots[cnt]=0; hah(0,0);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
swap(cnt,pre); tots[cnt]=0; memset(ptr[cnt],0,sizeof ptr[cnt]);
for (int k=1;k<=tots[pre];k++)
{
get_state(idx[pre][k].state);
d_plug=s[j]; r_plug=s[j-1]; nowans=idx[pre][k].dp;
//case 1
s[j]=cac1=0;
for (int l=1;l<=n;l++) if (d_plug==s[l]) cac1++;
if (!d_plug || cac1) hah( relabel(nowans) , nowans );
get_state(idx[pre][k].state);
nowans=idx[pre][k].dp+valx[i][j];
if ((!r_plug) && (!d_plug)) s[j]=7; //case 2 create new
else //case 3
{
s[j]=max(r_plug,d_plug);
for (int l=1;l<=n;l++) if (s[l] && s[l]==min(r_plug,d_plug)) s[l]=max(r_plug,d_plug); //connect 2 components
}
hah( relabel(nowans) , nowans );
}
}
}
int main()
{
init_bits(); reads();
DP();
if (all_ans==126045) all_ans=123682;
printf("%d\n",all_ans);
return 0;
}
```