题目：饼干
网址：http://noi-test.zzstep.com/contest/0x50「动态规划」例题/5105 Cookies
描述
圣诞老人共有M个饼干，准备全部分给N个孩子。每个孩子有一个贪婪度，第i个孩子的贪婪度为g[i]。如果有 a[i] 个孩子拿到的饼干数比第 i 个孩子多，那么第 i 个孩子会产生 g[i] * a[i]的怨气。给定N、M和序列g，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小。1≤N≤30, N≤M≤5000, 1<=gi <= (10^7)
。
输入格式
第一行两个整数N,M，第二行N个整数g1 ~ gN。
输出格式
第一行一个整数表示答案，第二行N个整数表示每个孩子分到的饼干数。本题有SPJ，若有多种方案，输出任意一种均可。
样例输入
样例输入1
3 20
1 2 3
样例输入2
4 9
2 1 5 8
样例输出
样例输出1
2
2 9 9
样例输出2
7
2 1 3 3
来源
ITMO
很具有特色的一道线性DP题目。
首先，这道题我们通过感觉发现：贪婪度越大的小朋友分得饼干数量越大，怨气总和越小。（这是题感，做题越多，越能感觉出来）
不妨考虑邻项交换（微扰）求证：不妨设当前第i个小朋友（排好序的）的贪婪度为a，比其饼干数多的人数为j，设当前第i + 1个小朋友贪婪度为b，比其饼干数多的人数为j - 1。
那么它们的饼干数量未交换时的怨气值为：a * j + b * (j - 1)；饼干数交换后怨气值为：a * (j - 1) + b * j
两式作差得：a - b。当a > b时，前者的怨气和大于后者的怨气和。相反，则后者的怨气和大于前者的。
于是，我们根据以上结论，将贪婪值由大到小进行排序，前面的小朋友分得数量>=后面的小朋友；而现在，若每个小朋友的饼干数都不相同，则怨气和的最小值只有一个。
下面针对分得每位小朋友的饼干数可能相同进行动态规划；
不妨设dp[i, j]代表前i个小朋友（排好序后的）分j个饼干的最小怨气和；
那么，怎么转移呢？对于第i个人，我们想确定其分配的饼干数目，但是，这并不能保证第i + 1个人分得的饼干数小于等于第i个人的数量（换句话说，根据结论，如果第i + 1个人大于等于第i个人的数目，其结果必然不如第i个人大于等于第i个人的数目优秀）；
还记得“数的划分”的DP版吗？对于当时的状态，我们通过讨论两种情况，保证相对大小不变进行转移。
同理，我们可以这样考虑：
- 当第i个人分得饼干数 > 1（即前i个人分的饼干数都大于1），那么每个人手中饼干数-1其相对大小不变，一定有dp[i, j] = dp[i, j - i]；
- 当第i个人分得饼干数 = 1，应向前枚举有多少人与他饼干数相等，那么把已经确定的饼干数为1的减去，则必有：dp[i, j] = min{dp[k, j - (i - k)] + k * $ displaystyle sum^{i}_{k + 1}{g[i]} $}；
不对啊！对于第2个转移，我们无法保证在前k个人中分得数目均大于1啊！！！譬如：dp[i, j] 转移至 dp[k, j - i + k] 时，dp[k, j - i + k] 接着转移至 dp[s, j - i + k - k + s] 中，会发现 dp[k, j - i + k]给部分人也分得了1个饼干了，而之前的k * (sum{g[p]})}，实际上并不满足共k个人分得饼干数目大于1。
看起来确实有问题，但不难思考发现：这种转移中会被淘汰。不妨考虑：上述假设的前提是(s, i]这一区间的小朋友分得饼干数都为1，而在dp[i, j]计算的时候，我们会先假设k个人分得饼干数>1，在之前计算贡献中我们乘的是k，而不是s，导致该状态转移至一个非最优的状态；但是，留意一点：这只是一种转换，一种映射，就是说假设第k + 1之后分得饼干数均为1时，等价于dp[k, j - (i - k)] + [k + 1, i]所产生的贡献，这是一个等价的变换；本题的最终答案只会跟饼干的相对大小有关，和绝对数量无关，对于；从其它不同的人数分得不同的饼干数目，一一映射至前面状态中。另一面可以观察到，在我们枚举k的整个过程，当k = s时直接转移会将这种情况过滤。不妨可以模拟一下。
对于方案来讲，直接逆推 + 模拟即可。
代码如下：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int SIZE = 5000 + 5;
struct node
{
int num;
int cur;//这里有个小技巧，排序前把当前小朋友的位置记下来，以便寻找方案。
} g[31];
int n, m, s[31] = {}, dp[31][SIZE];
int ans[SIZE];
struct cmp
{
inline bool operator () (const node& lhs, const node& rhs)
{
return lhs.num > rhs.num;
}
};
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++ i)
{
scanf("%d", &g[i].num);
g[i].cur = i;
}
sort(g + 1, g + n + 1, cmp());
for(int i = 1; i <= n; ++ i) s[i] = s[i - 1] + g[i].num;
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for(int i = 1; i <= n; ++ i)
{
for(int j = i; j <= m; ++ j)
{
int &ans = dp[i][j];
if(j > i) ans = min(ans, dp[i][j - i]);
for(int k = 0; k < i; ++ k)
{
ans = min(ans, dp[k][j - (i - k)] + k * (s[i] - s[k]));
}
}
}
printf("%d
", dp[n][m]);
int i = n, j = m;
int delta = 0;
while(i && j)
{
if(j > i && dp[i][j] == dp[i][j - i])
{
j -= i;
++ delta;
}
else
{
for(int k = 0; k < i; ++ k)
{
if(dp[i][j] == dp[k][j - (i - k)] + k * (s[i] - s[k]))
{
for(int p = k + 1; p <= i; ++ p)
{
ans[g[p].cur] = delta + 1;
}
j -= i - k, i = k;
break;
}
}
}
}
ans[g[1].cur] += j;
for(int i = 1; i <= n; ++ i) printf("%d ", ans[i]);
return 0;
}
这道题启发我们，可以使用其他算法（如贪心、Tarjan等特定的图论模型或精巧的数据结构）确定阶段及计算顺序；对于难以转移的状态，我们可以通过相对大小，对其进行转换。我们还知道，在输出方案的过程中，若时间复杂度允许，可以通过反推枚举，简化输出方案难度。