$UVA10559\ Blocks\ $区间$dp$

$Des$

• 有一排数量为N的方块，每次可以把连续的相同颜色的区间消除，得到分数为区间长度的平方，然后左右两边连在一起，问最大分数为多少。

• n<=1

$Sol$

正解状态设得奇奇怪怪巧巧妙妙.

$f[i][j][k]$表示区间$[i,j]$且$j$右边还有$k$个和$j$同色的方块,消除所有这些的最大分数.转移分为两种:

1.将右端点和多出的$k$个一起消掉,分数为$f[i][j-1]+(k+1)^2$.

2.选一个与右端点同色的点$p$,消掉$[p+1,j-1]$使得$p,j$相邻,分数为$f[i][p][k+1]+f[p+1][j-1][0]$.

那怎么样想到这个巧巧妙妙的状态呢:

首先这个题是有合并顺序的,可以考虑区间$dp$,考虑对于区间$[l,r]$能不能通过枚举中间点$k$,用$[l,k],[k+1][r]$转移.稍加思考就可以知道,这个亚子是不行的.这个题是"消消乐",可能中间的某个点会和边界一起消掉更优.于是就发现,这题并不是规规矩矩的区间$dp $,看能不能通过多记一维状态来解决这个问题...于是就聪聪明明地设出了这个状态强行.

这题好好写,瞎写一下就过了.

$Code$

Code

```cpp
#include
#include
#include
#define il inline
#define Ri register int
#define go(i,a,b) for(Ri i=a;i=b;--i)
#define e(i,u) for(Ri i=b[u];i;i=a[i].nt)
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define db double
#define inf 2147483647
using namespace std;
il int read()
{
Ri x=0,y=1;char c=getchar();
while(c'9'){if(c=='-')y=-1;c=getchar();}
while(c>='0'&&c

巴特西

$UVA10559\ Blocks\ $区间$dp$

\(Des\)

\(Sol\)

\(Code\)

最新文章

热门文章