输入第一行包含两个整数n，k（k+1≤n）。
输出第一行包含一个整数，为小H可以得到的最大分数。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define ll long long int using namespace std; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1}; int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1}; const int inf=0x3f3f3f3f; const ll mod=1e9+7; ll n,k; ll a[100007]; ll dp[100007][2]; ll sum[100007]; ll q[100007]; double slope(ll j,ll k,ll zu){ return sum[k]-sum[j]==0?0:((dp[j][zu]-sum[j]*sum[j]-dp[k][zu]+sum[k]*sum[k]) /(sum[k]-sum[j])); } int main(){ ios::sync_with_stdio(false); while(cin>>n>>k){ for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i]; int l,r; for(int j=1;j<=k;j++){ //分割次数 l=r=1; for(int i=1;i<=n;i++){ //人数 while(l<r&&slope(q[l],q[l+1],(j-1)%2)<sum[i]) l++; dp[i][j%2]=dp[q[l]][(j-1)%2]+sum[q[l]]*(sum[i]-sum[q[l]]); while(l<r&&slope(q[r-1],q[r],(j-1)%2)>slope(q[r],i,(j-1)%2)) r--; q[++r]=i; } } cout<<dp[n][k%2]<<endl; } return 0; }
原文：https://www.cnblogs.com/wmj6/p/10797847.html