题目描述
$pure$ 在玩一个战略类游戏. 现在有一个士兵方阵, 每行有若干士兵, 每个士兵属于某个兵种. 行的顺序不可改变, 且每一行中士兵的顺序也不可改变. 但由于每一行都有 $C$ 个位置 ($C$ 不小于任一行的士兵数), 她能够安排每行的士兵依次站在某几个位置上.
对于每一个士兵, 令其前后左右相邻四个位置上有 $v$ 个和他种类相同的士兵, 则 $pure$ 会获得 $v$ 的布阵分数. 现在 $pure$ 想知道她最多能够获得多少布阵分数.
输入格式
第一行包含两个整数 $R,C$, 分别表示行数, 以及每一行的位置数.
接下来 $R$ 行, 每行一个由大写字母构成的字符串, 同一字母的士兵为同一种类.
输出格式
一行一个整数, 表示 $pure$ 能够获得的最高布阵分数.
样例
样例输入:
2 5
ABBCD
AC
样例输出:
6
数据范围与提示
样例解释:
布阵如下:
ABBCD
A__C_
共获得 $6$ 分.
数据范围:
对于 $20\%$ 的数据,$R\leqslant 3,C\leqslant 4$;
对于 $40\%$ 的数据,$R\leqslant 16$;
对于 $100\%$ 的数据,$R\leqslant 128,C\leqslant 16$, 字符串长度不超过 $C$.
题解
我们可以只考虑左边和上边的格子, 因为兵种一样是相互的, 所以最后再乘 $2$ 即可.
先考虑暴力的状压, 无非就是枚举上一行的状态, 然后再枚举本行的状态, 取 $\max$, 时间复杂度是 $\Theta((C_C^{\frac{C}{2}})^2\times C\times R)$ 的.
然后, 我们发现, 瓶颈就在于枚举所有的状态, 所以我们可以利用轮廓线.
如果你打过插头 $DP$, 这将非常好理解, 枚举行变成了枚举单个格, 能对其作出贡献的只有其左边和上边的格了.
代码实现稍繁琐......
时间复杂度:$\Theta(2^C\times C\times 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++
[杂题]:group(状压 DP + 轮廓线)
来源: http://www.bubuko.com/infodetail-3217060.html