【UVA10559 方块消除 Blocks】题解

题目链接

首先先预处理，把连续方块合一，变成 P2135 方块消除。 没错这题是双倍经验

设 \(dp(i, j, k)\) 为区间 \([i, j]\) 内后面与 \(a[j]\) 相同颜色的方块有 \(k\) 个，然后分两种情况考虑。

1. 直接把 \([i, j-1]\) 裁掉，于是 \(dp(i, j, k)=dp(i, j-1, 0)+(b[j]+k)^2\)
2. 在 \([i, j-1]\) 区间内找一段 \(p\) 使得 \(a[p]=a[j]\)，于是 \(dp(i, j, k)=dp(i, p, k+b[j])+dp(p+1, j-1, 0)\)

可能解释得不太清，毕竟这道题我自己也还没完全吃透。

实现的话用记忆化搜索会方便点，直接放代码吧：

// Problem: UVA10559 方块消除 Blocks
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA10559
// Memory Limit: 0 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define mo
#define N 210
int n, m, i, j, k, t, p; 
int a[N], b[N], c[N]; 
int dp[N][N][N]; 

int dfs(int l, int r, int k)
{
	if(dp[l][r][k]!=-1) return dp[l][r][k]; 
	int sum=b[r]+k; 
	if(l==r) return dp[l][r][k]=sum*sum; 
	int ans=dfs(l, r-1, 0)+sum*sum; 
	for(int i=l; i