C. Sweets Eating(DP)

106 阅读 0 评论 70 点赞

我是靠谱客的博主友好音响，这篇文章主要介绍C. Sweets Eating(DP)，现在分享给大家，希望可以做个参考。

永远的传送大门校门中门

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

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

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

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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;
}