C. Sweets Eating(DP)

103 阅读 0 评论 68 点赞

我是靠谱客的博主友好音响，最近开发中收集的这篇文章主要介绍C. Sweets Eating(DP)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

永远的传送大门校门中门

$先按照甜度从小到大排序$

$设 d p [i] 为吃 i 块蛋糕的最小甜度$

$那么第 i 块蛋糕在第 1 天吃， [i - m + 1, i] 都在第一天吃$

$[1, i - m] 吃的天数都晚了 1 ，所以加上他们的前缀和。$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200009],n,m,ans;
ll f[200009],sumn[200009];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)
	{
		sumn+=a[i];
		if(i<m)	dp[i]=sumn;
		else	dp[i]=dp[i-m]+sumn;//前i-m天要多加1次 
		cout<<dp[i]<<" ";
	}
	return 0;
}