[BZOJ1587]叶子合并leaves-布布扣-bubuko.com

Description

在一个美丽的秋天，丽丽每天都经过的花园小巷落满了树叶，她决定把树叶堆成K堆，小巷是笔直的共有N片树叶（树叶排列也是笔直的），每片树叶都有一个重量值，并且每两片想邻的树叶之间的距离都是1 现把所有的树叶按从左到右的顺序进行编号，编号为1..N。丽丽移动每片树叶所消耗能量等于这片树叶的重量乘以移动的距离，丽丽决定分K天完成，每天堆一堆，并且规定只能把树叶往左移动，因为丽丽每天都是从右往左经过小巷的。求丽丽完成任务所消耗的最少能量。

Input

输入的第一行为两个用空格隔开的正整数N和K。后面有N行每行一个正整数表示叶子的重量（第i+1行表示第i片树叶的重量）

Output

输出为一个整数，表示把树叶堆成K堆所消耗的最少体力。

Sample Input

5 2
1
2
3
4
5

Sample Output

HINT

N在(0,1001)
K在(0,11)
每片树叶的重量(0,1001)

前缀和优化一下即可

还要注意一下叶子们的顺序

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define M 1001
 5 #define ll long long
 6 using namespace std;
 7 int n,K;
 8 int h[M];
 9 ll pre[M];//前缀和 
10 ll sum[M][M];//表示把1-i的叶子搞到j的费用 
11 ll dp[M][11];//表示前i堆叶子分了j段的最小费用 
12 int main()
13 {
14     scanf("%d%d",&n,&K);
15     for(int i=1;i<=n;i++) scanf("%d",&h[i]);
16     for(int i=1;i<=n/2;i++) swap(h[i],h[n-i+1]);
17     for(int i=1;i<=n;i++) pre[i]=pre[i-1]+h[i];
18     for(int i=1;i<=n;i++)
19         for(int j=i;j<=n;j++)
20         {
21             if(i==j) sum[i][j]=sum[i-1][j-1]+pre[i-1];
22             else sum[i][j]=sum[i][j-1]+pre[i];
23         }
24     memset(dp,0x7f,sizeof(dp));
25     for(int i=1;i<=n;i++)
26     {
27         dp[i][1]=sum[i][i];
28         for(int j=1;j<i;j++)
29             for(int k=2;k<=min(K,j+1);k++)
30                 dp[i][k]=min(dp[i][k],dp[j][k-1]+sum[i][i]-sum[j][i]);
31     }
32     printf("%lld",dp[n][K]);
33     return 0;
34 }

[BZOJ1587]叶子合并leaves

原文：https://www.cnblogs.com/Slrslr/p/9575473.html