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

13

HINT

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

前缀和优化一下即可

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

代码:

 #include<iostream>
#include<cstdio>
#include<cstring>
#define M 1001
#define ll long long
using namespace std;
int n,K;
int h[M];
ll pre[M];//前缀和
ll sum[M][M];//表示把1-i的叶子搞到j的费用
ll dp[M][];//表示前i堆叶子分了j段的最小费用
int main()
{
scanf("%d%d",&n,&K);
for(int i=;i<=n;i++) scanf("%d",&h[i]);
for(int i=;i<=n/;i++) swap(h[i],h[n-i+]);
for(int i=;i<=n;i++) pre[i]=pre[i-]+h[i];
for(int i=;i<=n;i++)
for(int j=i;j<=n;j++)
{
if(i==j) sum[i][j]=sum[i-][j-]+pre[i-];
else sum[i][j]=sum[i][j-]+pre[i];
}
memset(dp,0x7f,sizeof(dp));
for(int i=;i<=n;i++)
{
dp[i][]=sum[i][i];
for(int j=;j<i;j++)
for(int k=;k<=min(K,j+);k++)
dp[i][k]=min(dp[i][k],dp[j][k-]+sum[i][i]-sum[j][i]);
}
printf("%lld",dp[n][K]);
return ;
}
05-11 20:56