链接：https://ac.nowcoder.com/acm/contest/15397/B
来源：牛客网
小Z为训练营同学预订了n（1≤n≤500）个回程航班，每个航班的同学数依次为a1,a2,…,an(1≤ai≤106)。现在只有一个司机，司机需要严格按照航班顺序依次将第1到第n个航班的同学送往机场。该司机可从租车公司租到任意载客量的车，但是最多只能租g次(1<=g<=n)，并且每次只能租1辆。假设司机用载客量为m的车送ai个同学到机场（当然要求不超载），那么就造成了m-ai的载量浪费。请问该司机送完所有批次同学到机场后，最低的载量浪费是多少？

将数组分成g+1份，求怎么分可以使(maxi*leni) - sumi之和最小。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 510;
const ll mod = 100000007;
const int INF = 1e9;
int n,m;
int a[maxn];
int sum[maxn],Max[maxn][maxn];
int dp[maxn][maxn];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];

    /* 求区间最大值 */
    for(int i=1;i<=n;i++)    
    {
        Max[i][i]=a[i];
        for(int j=i+1;j<=n;j++)
        Max[i][j]=max(Max[i][j-1],a[j]);
    }

    //初始化数组
    for(int i=0;i<maxn;i++)
        for(int j=0;j<maxn;j++)
            dp[i][j]=INF;
    dp[0][0]=0;

    for(int i=1;i<=n;i++)
    {
        for(int k=0;k<i;k++)
        {
            for(int j=0;j<m;j++)
                dp[i][j+1]=min(dp[i][j+1],dp[k][j]+ Max[k+1][i]*(i-k) - (sum[i]-sum[k]) );    
        }
    }
    int ans=INF;
    for(int j=0;j<=m;j++) ans=min(ans,dp[n][j]);
    printf("%d",ans);
    return 0;
}