[2011山东ACM省赛] Sequence （动态规划）

Sequence

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

Given an integer number sequence A of length N (1<=N<=1000), we define f(i,j)=(A[i]+A[i+1]+...+A[j])^2 (i<=j).
Now you can split the sequence into exactly M (1<=M<= N) succesive parts, and the cost of a part from A[i] to A[j] is f(i,j). The totle cost is the sum of the cost of each part. Please split the sequence with the minimal cost.

输入

At the first of the input comes an integer t indicates the number of cases to follow. Every case starts with
a line containing N ans M. The following N lines are A[1], A[2]...A[N], respectively. 0<=A[i]<=100 for every 1<=i<=N.

输出

For each testcase, output one line containing an integer number denoting the minimal
cost of splitting the sequence into exactly M succesive parts.

示例输入

1
5 2
1 3 2 4 5

示例输出

117

提示

来源

山东省第二届ACM大学生程序设计竞赛

解题思路：

代码：

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn=1010;
int num[maxn];
long long sum[maxn];
long long dp[maxn];

int min(int a,int b)
{
    return a>b?b:a;
}

int main()
{
    int t;cin>>t;
    int n,m;
    while(t--)
    {
        memset(sum,0,sizeof(sum));
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>num[i];
            sum[i]=sum[i-1]+num[i];
            dp[i]=sum[i]*sum[i];//求前i个数和的平方，这一句也是为什么dp数组不用初始化为最大值的原因
        }
        for(int i=2;i<=m;i++)//划分为几部分
        {
            for(int j=n-m+i;j>=i;j--)//从dp[n-m+i]出开始更新，从后往前，要构成更多的划分，因此dp[n-m+i]后面的dp[]不用更新，更新了也用不到
            {
                for(int k=i-1;k<j;k++)//从哪里到哪里的划分，上一次的dp[]划分加上新的划分区间和，枚举，取最小值
                {
                    dp[j]=min(dp[j],dp[k]+(sum[j]-sum[k])*(sum[j]-sum[k]));
                    if(i==m&&k==j-1)//计算到划分为m部分，且枚举完毕
                       goto label;
                }
            }
        }
        label:
        cout<<dp[n]<<endl;
    }
    return 0;
}