CF1312E Array Shrinking
chen_qian
2021-01-31 20:51:40
[题目链接](https://www.luogu.com.cn/problem/CF1312E)
这里有一个性质，就是对于一个区间$[l,r]$，如果它可以被缩成一个数，那么这个数是一定的。
知道了这个结论，我们要做就是，确定一个区间是否能合并成一个数，如果能，那么这个数是多少？
假设这个区间是$[l,r]$,
在本题中，很容易想到一个区间DP的思路，枚举一个中间点$k$。假如说，$[l,k]$与$[k+1,r]$都可以合成一个数$x$,那么$[l,r]$就可以合成一个数$x+1$了，这时就有一个无法回避的问题，就是我们必须要确定合成的数，这时一般有两种处理方式：
1.将这个数作为$dp$方程的一维，用枚举来确定
2.将其作为$dp$的目标
这里显然使用后者。所以设$f[l][r]$表示将区间$[l,r]$合成成一个数后其值为多少。$f[l][r]=0$就表示其不能合成一个数。
那么就有
$f[l][r]=f[l][k]+1 (f[l][k]=f[k+1][r]$)
简单区间$dp$即可
但是这并不是我们要求的答案。
不过既然我们都求出每个区间能不能合成一个数，那么就$dp[i]$表示$[1,i]$合成最短的长度。
那么就有
$dp[i]=\min_{f[j][i]>0}(dp[j-1]+1)$
```
#include<bits/stdc++.h>
#define N 505
using namespace std;
int n,f[N][N],a[N];
int dp[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) f[i][i]=a[i];
for(int len=2;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
for(int i=l;i<r;i++)
if(f[l][i]&&f[l][i]==f[i+1][r]) f[l][r]=f[l][i]+1;
}
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
if(f[j][i]) dp[i]=min(dp[j-1]+1,dp[i]);
}
}
printf("%d",dp[n]);
return 0;
}
```
总结：
对于比较难的$dp$题往往不以题面所要求的目标作为目标，而是进行一些目标的转换。一般有以下两种情况。
1. 利用容斥，取题面目标的反面。
1. 如本题，将要想求得题面目标所需要处理的信息进行处理。