SDUT 2169 Sequence dp 디스패치

#include<bits/stdc++.h>
#define LL long long
#define INF 0x3f3f3f3f

using namespace std;

LL dp[1010][1010];
LL sum[1010];
int main()
{
    int T;
    while(~scanf("%d",&T))
    {
        while(T--)
        {
            int n,m;
            scanf("%d%d",&n,&m);
            int a;
            memset(dp,INF,sizeof(dp));
            dp[0][0]=0;
            for(int i=0;i<=m;i++)
                dp[i][0]=0;
            for(int i=0;i<=n;i++)
                dp[0][i]=0;

            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a);
                sum[i]=sum[i-1]+a;
                dp[1][i]=sum[i]*sum[i];  /// i      
            }

            for(int i=2;i<=m;i++)
            {                ///       ///j<=n-m+i：   n    m      n    m-1    ，
                                          ///            n-1    m-1 ，  ；   n   m-1,m-2,m-3,m-4...      
                for(int j=i;j<=n-m+i;j++)    
                {
                    for(int k=i-1;k<=j-1;k++)
                    {
                        dp[i][j]=min(dp[i][j],dp[i-1][k]+(sum[j]-sum[k])*(sum[j]-sum[k]));
                    }
                }
            }
            printf("%lld
",dp[m][n]);
            ///      
            
            
///            
///            for(int i=2;i<=m;i++)   ///  
///            {               
///                                      
///                for(int j=i;j<=n-m+i;j++)    
///               {
///                    for(int k=j-1;k>=i-1;k--)     ///  
///                    {
///                           if((sum[j]-sum[k])*(sum[j]-sum[k])>=dp[i][j]) break;         ///    ，         。

///                        dp[i][j]=min(dp[i][j],dp[i-1][k]+(sum[j]-sum[k])*(sum[j]-sum[k]));
///                    }
///                }
///            }
///            printf("%lld
",dp[m][n]);

        }
    }
    return 0;
}