sdut2169Sequence(dp)

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2169

感觉是有递归思想的 dp[j]表示从1到j分成了i段最多分成m段肯定是分的越多越小的第一重循环为（1，m）

dp[j] = min(dp[j],dp[g]+pow(sum[g..j]);

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<cmath>
 7 using namespace std;
 8 #define N 1010
 9 #define INF 0xfffffff
10 #define LL long long
11 LL dp[1010];
12 LL sum[1010];
13 int a[1010];
14 int main()
15 {
16     int t,i,j,n,m,g;
17     cin>>t;
18     while(t--)
19     {
20         memset(sum,0,sizeof(sum));
21         cin>>n>>m;
22         for(i = 1 ; i <= n ; i++)
23         dp[i] = INF;
24         for(i = 1; i <= n ; i++)
25         {
26             cin>>a[i];
27             sum[i] = sum[i-1]+a[i];
28             dp[i] = sum[i]*sum[i];
29         }
30         for(i = 2; i <= m ; i++)
31         {
32             for(j = n-m+i ; j >= i ; j--)
33             {
34                 for(g = i-1 ; g < j ; g++)
35                 dp[j] = min(dp[j],dp[g]+(sum[j]-sum[g])*(sum[j]-sum[g]));
36             }
37         }
38         cout<<dp[n]<<endl;
39     }
40     return 0;
41 }

View Code