CF1312E Array Shrinking

题目链接

这里有一个性质，就是对于一个区间[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就表示其不能合成一个数。

那么就有

#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. 利用容斥，取题面目标的反面。
2. 如本题，将要想求得题面目标所需要处理的信息进行处理。