题目描述
$pure$在玩一个战略类游戏。现在有一个士兵方阵，每行有若干士兵，每个士兵属于某个兵种。行的顺序不可改变，且每一行中士兵的顺序也不可改变。但由于每一行都有$C$个位置（$C$不小于任一行的士兵数），她能够安排每行的士兵依次站在某几个位置上。
对于每一个士兵，令其前后左右相邻四个位置上有$v$个和他种类相同的士兵，则$pure$会获得$v$的布阵分数。现在$pure$想知道她最多能够获得多少布阵分数。
输入格式
第一行包含两个整数$R,C$，分别表示行数，以及每一行的位置数。
接下来$R$行，每行一个由大写字母构成的字符串，同一字母的士兵为同一种类。
输出格式
一行一个整数，表示$pure$能够获得的最高布阵分数。
样例
样例输入：
2 5
ABBCD
AC
样例输出：
6
数据范围与提示
样例解释：
布阵如下：
ABBCD
A__C_
共获得$6$分。
数据范围：
对于$20\%$的数据，$Rleqslant 3,Cleqslant 4$；
对于$40\%$的数据，$Rleqslant 16$；
对于$100\%$的数据，$Rleqslant 128,Cleqslant 16$，字符串长度不超过$C$。
题解
我们可以只考虑左边和上边的格子，因为兵种一样是相互的，所以最后再乘$2$即可。
先考虑暴力的状压，无非就是枚举上一行的状态，然后再枚举本行的状态，取$max$，时间复杂度是$Theta((C_C^{frac{C}{2}})^2 imes C imes R)$的。
然后，我们发现，瓶颈就在于枚举所有的状态，所以我们可以利用轮廓线。
如果你打过插头$DP$，这将非常好理解，枚举行变成了枚举单个格，能对其作出贡献的只有其左边和上边的格了。
代码实现稍繁琐……
时间复杂度：$Theta(2^C imes C imes R)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
int r,c;
char ch[20];
int Map[150][20];
int Mapl[100000][20],Mapr[100000][20];
int dp[2][100000];
bool now;
int ans;
int main()
{
scanf("%d%d",&r,&c);
for(int i=1;i<=r;i++)
{
scanf("%s",ch+1);
Map[i][0]=strlen(ch+1);
for(int j=1;j<=Map[i][0];j++)
Map[i][j]=ch[j]-'A'+1;
}
memset(dp,-0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=0;i<(1<<c);i++)
{
for(int j=2;j<=c+1;j++)
Mapl[i][j]=Mapl[i][j-1]+(i&(1<<(j-2))?1:0);
for(int j=c-1;j;j--)
Mapr[i][j]=Mapr[i][j+1]+(i&(1<<j)?1:0);
}
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
now^=1;
memset(dp[now],-0x3f,sizeof(dp[now]));
for(int k=0;k<(1<<c);k++)
{
if(Map[i][Mapl[k][j]+1])
dp[now][((((k>>j)<<1)|1)<<(j-1))|(k&((1<<(j-1))-1))]=max(dp[now][((((k>>j)<<1)|1)<<(j-1))|(k&((1<<(j-1))-1))],dp[!now][k]+(((k&(1<<j-2))?Map[i][Mapl[k][j]]:0)==Map[i][Mapl[k][j]+1])+(((k&(1<<j-1))?Map[i-1][Map[i-1][0]-Mapr[k][j]]:0)==Map[i][Mapl[k][j]+1]));
dp[now][((((k>>j)<<1)|0)<<(j-1))|(k&((1<<(j-1))-1))]=max(dp[now][((((k>>j)<<1)|0)<<(j-1))|(k&((1<<(j-1))-1))],dp[!now][k]);
}
}
for(int j=0;j<(1<<c);j++)
if(Mapl[j][c+1]!=Map[i][0])dp[now][j]=-0x3f3f3f3f;
}
for(int i=0;i<(1<<c);i++)
ans=max(ans,dp[now][i]);
printf("%d",(ans<<1));
return 0;
}
rp++