[USACO18DEC]Teamwork
https://www.luogu.org/problemnew/show/P5124
题意：n个数，最多k个一组，划分必须是连续的，求一个划分方案：用区间最大值代替区间的每一个值后所有区间的和是最大的。
思路：线性dp，设f(i):前i个元素的最优值，f(i)=max{f(i-x)+[i-x+1~i]},x∈[1,k]
#include
using namespace std;
#define maxn 100000+100int n,k,a[maxn],f[maxn];int main()
{
// freopen("input.in","r",stdin);cin>>n>>k;for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){int maxx=a[i];for(int j=i-1;i-j<=k&&j>=0;j--){f[i]=max(f[i],f[j]+maxx*(i-j));maxx=max(maxx,a[j]);}}cout<
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！