解析

這題可以轉化一下：

（《神筆馬良》。。。。）
計算這些長方形對應下標的總加和
我們可以一層一層往上壘,假設第i層起始點為xi，總和為sumi，再設從1到i的前綴和為si
顯然第一層x1=1，sum1=sn
對于第二層x2，sum2=tot[x2,n]=sn-s[x2-1]
對于第三層x3，sum3=sn-s[x3-1]
。。。
對于第k層xk，sumk=sn-s[xk-1]
最后累加sum即答案
顯然答案整理一下應為k*sn-(s[x2-1]+s[x3-1]+…+s[xk-1])
要使ans最大，顯然要使括號內最小
那么我們只需找出最小的k-1個（因為第一層不減）最小的前綴和再用k*sn減去他們即可
注意因為xk<=n,xk-1<n-1,所以sn是不能作為減數的

代碼

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> #include<string> #include<queue> #include<vector> using namespace std; int n,k; int a[300500]; long long s[300500]={ }; bool cmp(long long x,long long y){return x<y; } int main(){scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&a[i]);s[i]=s[i-1]+a[i];}long long ans=s[n]*k;sort(s+1,s+n,cmp);//最后一個不能取 for(int i=1;i<=k-1;i++){ans-=s[i];}printf("%lld\n",ans);return 0; }

AC快樂！！！

總結

以上是生活随笔為你收集整理的贪心： Array Splitting（数列分段）（洛谷CF1175D）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。