第一次过 Div2 E，然鹅 C 挂了......

题目链接：CF1312E 【Array Shrinking】

本人在这道题上花了 $1h$，但实际上看起来并没有那么的难

我们很快可以发现：

在最终数组中，某一个数字一定是原数组中连续的一段。

并且容易看出，某一段如果可以缩成一个点，则这个数字是固定的

这样的话，状态就很好设置了：

定义 $dp[i][j]$ 为 $[i,j]$ 缩为一个数字后，这个数字是多少

如果不能缩成一个数字，值为 $0$

那么我们就有转移：

$$dp[i][j] = dp[i][k] + 1$$

$$ (i \le k < j,dp[i][k] = dp[k + 1][j] \neq 0)$$

这明显是一个区间 $dp$，时间复杂度为 $O(n^3)$

这样我们就可以得到所有能够缩成一个数字的区间了

接下来我们所需要做的，就是把所有数字分割为若干段，满足每一段都能被缩成一个数字，且段的个数最小

这又是一个简单的 $dp$，复杂度为 $O(n^2)$

然后我们就做完啦！

$Code:$

//Code By CXY
#include<bits/stdc++.h>
using namespace std;
    
const int MAXN = 510;
     
int n;
int a[MAXN];
int dp1[MAXN][MAXN],dp2[MAXN]; 
     
signed main () {
      scanf("%d",&n);
       for(register int i = 1;i <= n; ++i)
           scanf("%d",&a[i]),dp1[i][i] = a[i];
       for(register int l = 2;l <= n; ++l) {//注意枚举的是区间长度！
           for(register int i = 1,j;i + l - 1 <= n; ++i) {
               j = i + l - 1;
               for(register int p = i;p < j; ++p)
                   if(dp1[i][p] && dp1[i][p] == dp1[p + 1][j]) dp1[i][j] = dp1[i][p] + 1;    
           }
       }
       for(register int i = 1;i <= n; ++i) {
           dp2[i] = i;
           for(register int j = 1;j <= i; ++j)
               if(dp1[j][i]) dp2[i] = min(dp2[i],dp2[j - 1] + 1);
       }
       cout << dp2[n] << endl;
       return 0;//End.
}

所以这道题其实不是很难的样子，然鹅我考场竟然还妄想了一波贪心

还是太弱了......

初三的 $OIer$，请多关照