原题链接：Problem - 1253C - Codeforces

题目大意： 糖果每天最多吃m个，一共n个糖果。糖果第d天吃的花费是a[i] * d 问你吃k块糖果的最小花费是多少。

思路：先把每颗糖果的a[i]排序，例如1 2 3 4 5..比如m为3，一天最多吃三颗糖。那么如果要吃1颗糖，当然选择最少的，而且在第一天吃，花费就是1；如果2颗，2 <= 3，都在第一天吃，所以1 + 2 = 3..如果4颗，肯定让4 3 2在第一天吃，1 在第二天吃，那么答案就是4 +3 + 2 + 1 * 2..

前缀和:每颗糖果都加一遍的结果。

状态转移方程：

if(i <= m) dp[i] = s[i];
else dp[i] = s[i] + dp[i - m];

其实也是一个递归的思想，每m个糖果一周期，看代码：

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
typedef pair<int, int> PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = n; i >= (1); --i)
typedef long long ll;
#define sqar(x) ((x)*(x))
const int N = 2e5 + 10;
ll s[N];
ll dp[N];
int main(){
int n, m;
cin >> n >> m;
rep(i, n) cin >> s[i];
sort(s + 1, s + 1 + n);
rep(i, n) s[i] += s[i - 1];
rep(i, n){
if(i <= m) dp[i] = s[i];
else dp[i] = s[i] + dp[i - m];
cout << dp[i] << " ";
}
return 0;
}

最后

以上就是魁梧煎饼为你收集整理的C. Sweets Eating（cf）dpAC代码：的全部内容，希望文章能够帮你解决C. Sweets Eating（cf）dpAC代码：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。