区间dp

虚拟比赛时没有做出来，看题解时，第一句话就让我反应过来了！
可恶！！！！

最终的答案假如[a1,a2,a3]那么a1,a2,a3一定是三个区间合并出来的
也就是，我们给数组划分几个区间，这些区间都可以合并成一个数。
找到划分区间的最小数。

问题一下子就简化了！！
定义dp[i][j]，如果[i,j]不可以合并成一个数那么dp[i][j]=inf
否则dp[i][j] = 最终合并的这个数
转移dp[i][j]=dp[i][k]+1 if dp[i][k]!=inf&&dp[k+1][j]!=inf&&dp[i][k]==dp[k+1][j]
其实就是划分更两个区间看。
当dp维护成功时，其实最终答案也就出来了。
再来一次dp
ans[i]为[1,i]操作中的最少剩余元素
如果dp[1][i]!=inf ans[i]=1
否则枚举更新ans[i] = min(ans[j]+1 if dp[j+1][i]!=inf)
答案就是ans[n]了

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf = 1e9;
int dp[600][600];
int res[600];
int main(){
    int n;scanf("%d",&n);
    for (int i=1;i<=n;++i)for (int j=1;j<=n;++j)dp[i][j]=inf;
    for (int i=1;i<=n;++i)scanf("%d",&dp[i][i]);
    for (int len = 2;len<=n;++len){
        for (int i=1;i+len-1<=n;++i){
            int lft = i,rgt = i+len-1;
            for (int j=lft;j<rgt;++j){
                if (dp[lft][j]!=inf&&dp[lft][j]==dp[j+1][rgt]){
                    dp[lft][rgt] = dp[lft][j]+1;
                    break;
                }
            }
        }
    }
    for (int i=1;i<=n;++i)res[i]=inf;
    for (int i=1;i<=n;++i){
        if (dp[1][i]!=inf){
            res[i]=1;
            continue;
        }
        for (int j=i-1;j>=0;--j)
            if (dp[j+1][i]!=inf)
                res[i]=min(1+res[j],res[i]);
    }
    printf("%d\n",res[n]);
}