Educational Codeforces Round 83 Array Shrinking

题意：
每次可以选择相邻并且相等的数合并变成一个数，该数的值为该值+1，问怎样合并使得最后数组最少

我区间dp太弱了，看不出来，状态转移就是单纯的
另外额外开一个二维a数组 记录l～r之间是否能合并,并记录合并完的结果
如果l~r之间能合并 那么直接合并把dp[l][r]变成1就行了。

    #include<iostream>
    #include<cstring>
    using namespace std;
    int dp[510][510];
    int a[510][510];
    int main()
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i][i];    
        memset(dp,0x3f,sizeof dp);
        for(int i=1;i<=n;i++)
            dp[i][i]=1;
        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++)
                {
                    dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
                    if(a[l][k]==a[k+1][r] && dp[l][k]==1 && dp[k+1][r]==1)
                        dp[l][r]=1,a[l][r]=a[l][k]+1;
                }
            }
        cout<<dp[1][n]<<endl;
    }