「CH 5105」Cookies (DP + 输出方案)

CH 5105
题意:有$n$个人,每个人有一个$g_i$,现给$n$人分配$m$个饼干(每个人都要有饼干),对于第$i$个人,比他饼干多的人数记为$a_i$,请最小化$\sum_{i=1}^n a_i g_i$

容易发现$g_i$大的$a_i$尽可能小,所以$g_i$单调递减时分配的饼干也单调递减。
对$g$降序排序后,设$dp(i,j)$为前$i$个人合分$j$块饼干的最小值。
则有
$$
dp(i,j)=min(dp(i,j-i), min_{0 \leq k < i}(dp(k, j - (i - k)) + k \cdot \sum_{x=k+1}^ig(x)))
$$

当第$i$位不填$1$时,前$i$个人分$j$块对应于前$i$个人分$j-i$块,因为每个人少拿一块,相对关系不变
否则,枚举前面有几个和它一样的,统计答案。

注意解的输出要按照dp意义来,注意递归输出在本题会好用些。

知识点:
1、DP 输出方案要按照dp意义来。并且有时候递归输出方便。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int INF = 1000000000;
struct data {
int g, id;
} c[35];
int n, m, dp[35][5005], pre[35][5005][2], sum[35], ans[35];
bool cmp(data a, data b) {return a.g > b.g;}
void print(int x, int y) {
if (x == 0 || y == 0) return ;
print(pre[x][y][0], pre[x][y][1]);
if (pre[x][y][0] == x) {
for (int i = 1; i <= x; ++i) ++ans[c[i].id];
} else for (int i = pre[x][y][0] + 1; i <= x; ++i) ans[c[i].id] = 1;
}
void clean() {
ms(pre, -1), ms(ans, 0);
}
int solve() {
clean();
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> c[i].g, c[i].id = i;
sort(c + 1, c + 1 + n, cmp);
sum[0] = 0;
for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + c[i].g;
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= m; ++j) dp[i][j] = INF;
dp[0][0] = 0;
for (int i = 0; i <= n; ++i) {
for (int j = i; j <= m; ++j) {
if (dp[i][j - i] < dp[i][j])
dp[i][j] = dp[i][j - i], pre[i][j][0] = i, pre[i][j][1] = j - i;
for (int k = 0; k < i; ++k) {
if (dp[k][j - (i - k)] + k * (sum[i] - sum[k]) < dp[i][j])
dp[i][j] = dp[k][j - (i - k)] + k * (sum[i] - sum[k]), pre[i][j][0] = k, pre[i][j][1] = j - (i - k);
}
}
}
printf("%d\n", dp[n][m]);
print(n, m);
for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------