hdu4283 区间dp

转移方程：dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]+(sum[j]-sum[k])*(k-i+1)+a[i]*(k-i));

一开始思路好像出了一点问题，我是考虑每次更新时把k放到第j个位置，然后k+1到j整体前移，但是不知道错在哪里了，

正解是，对于转移方程应该是每次把i放到第k的位置，更新从k+1到j 的位置

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define C 0.5772156649
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1

using namespace std;

const double g=10.0,eps=1e-7;
const int N=500+10,maxn=60000+10,inf=0x3f3f3f;

ll a[N],sum[N],dp[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t,cnt=0;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        sum[0]=0;
        for(int i=1; i<=n; i++)
        {
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
        }
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                dp[i][j]=1e18;
        for(int len = 1 ; len <= n-1 ; len ++)
        {
            for(int i=1,j=len+i;j<=n;i++,j++)
            {
                for(int k=i; k<=j; k++)
                {
                   // cout<<k<<endl;
                    dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]+(sum[j]-sum[k])*(k-i+1)+a[i]*(k-i));
                  //  cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
                }
            }
        }
        cout<<"Case #"<<++cnt<<": "<<dp[1][n]<<endl;
    }
    return 0;
}
/********************
2
5
1 2 3 4 5
5
5 4 3 2 2
put i into the dark room
dp   i ... k-1 k+1 ... j   k
id i-1 ... k-2 k-1 ... j-2 j-1
********************/