[acw277] Cookies

标签： 线性DP 贪心 排序

题目：

圣诞老人共有M个饼干，准备全部分给N个孩子。

每个孩子有一个贪婪度，第 i 个孩子的贪婪度为 g[i]。

如果有 a[i] 个孩子拿到的饼干数比第 i 个孩子多，那么第 i 个孩子会产生 g[i]*a[i]的怨气。

给定N、M和序列g，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小。

输入格式

第一行包含两个整数N,M。

第二行包含N个整数表示g1~gN。

输出格式

第一行一个整数表示最小怨气总和。

第二行N个空格隔开的整数表示每个孩子分到的饼干数，若有多种方案，输出任意一种均可。

数据范围

1≤N≤30,
N≤M≤5000,
1≤gi≤107

输入样例：

3 20
1 2 3

输出样例：

2
2 9 9

分析：

这是一道$O(n^2m)$
首先我们可以贪心地知道使$g[i]$越大的，给尽可能多的饼干
所以我们要先对g数组递减排序，饼干数递减分配，注意要记录在原始顺序中的位置，因为最后要输出方案
其次，我们就可以轻松地得出状态表示：

状态：

$F[i,j]表示给了前i个孩子，分了j个饼干时怨气最小值$

然后很难突破的是如何进行转移：

首先我们思考在转移中当前的最值与前面每个孩子的饼干数有关系，而每个孩子最少要有一个饼干那么，在转移$F[i,j]$时，我们可以思考第i个孩子饼干数为1和不为1两种情况。

• 对于为大于1的情况，因为是递减，前面每个孩子饼干数均大于1，故将前面每个孩子饼干数都减一，相对的大小关系不变，此时可以由$F[i,j-i]$转移
• 对于等于1的情况，可以进行枚举前面孩子中有几个饼干数也为1，因为是递减，我们只需要枚举一个$k$，表示从$k+1$到$i$的孩子饼干数都为1，从$F[k,j-(i-k)]$转移

转移：

$F[i,j] = min (F[i,j-i],min_{0<=k<i}{F[k,j-(i-k)]+k*\sum_{p=k+1}^{i}{g[p]}})$

边界：

$F[0,0] = 0$

目标：

$F[n,m]$

方案：

用与DP数组大小相同的结构体储存$F[i,j]$由那个状态转移，并递归求解，注意要先往下递归在计算当前的ans，因为每个$F[i,j]$是在上一个状态的基础上进行累加的

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 31;
const int MAXM = 5001;
int n, m;
int f[MAXN][MAXM], sum[MAXN], ans[MAXN];
struct val
{
    int t, pos;
} g[MAXN];
struct node
{
    int x, y;
} to[MAXN][MAXM];
bool cmp(val a, val b)
{
    return a.t > b.t;
}
void getans(int x, int y)
{
    if (x == 0)
        return;
    getans(to[x][y].x, to[x][y].y);
    if (x == to[x][y].x)
    {
        for (int i = 1; i <= x; i++)
            ans[g[i].pos]++;
    }
    else
    {
        for (int i = to[x][y].x + 1; i <= x; i++)
            ans[g[i].pos] = 1;
    }

    return;
}
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &g[i].t);
        g[i].pos = i;
    }
    sort(g + 1, g + n + 1, cmp);

    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + g[i].t;
        for (int j = i; j <= m; j++)
        {
            f[i][j] = f[i][j - i];
            to[i][j].x = i, to[i][j].y = j - i;
            for (int k = 0; k < i && i - k <= j; k++)
                if (f[i][j] > f[k][j - (i - k)] + k * (sum[i] - sum[k]))
                {
                    f[i][j] = f[k][j - (i - k)] + k * (sum[i] - sum[k]);
                    to[i][j].x = k, to[i][j].y = j - (i - k);
                }
        }
    }
    printf("%d\n", f[n][m]);
    getans(n, m);
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
    return 0;
}