CF1312E 区间DP

读完之后知道应该是区间DP（复杂度很适合，而且模型也像）但是想不出怎么同时处理合并和长度最小的问题。

想了很久还是没什么想法，然后去看了题解，其实就开两个DP数组同步做，同时处理l,r之间合并后的数字以及期间的最小长度就行了。

具体代码如下：

#include<bits/stdc++.h>
using namespace std;
const int INF=0X3f3f3f3f;
int dp[505][505],num[505][505],a[505],n;
int main(){
    memset(dp,INF,sizeof(dp));
    scanf("%d",&n);
    for (int i=1; i<=n; i++){
        scanf("%d",&a[i]);
        dp[i][i]=1;
        num[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 k=l; k<r; k++){
                if (dp[l][k]==1 && dp[k+1][r]==1 && num[l][k]==num[k+1][r]){
                    dp[l][r]=1;
                    num[l][r]=num[l][k]+1;    
                }
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
            }
        }
    }
    printf("%d",dp[1][n]);
}