思路

这么一道无序的题目,怎么弄出来的DP!

经过$lyd$的玄学引导,详见蓝书。

可以尝试将$g_i$从大到小排序,因为贪婪值较大的,拥有的饼干越多,对答案的贡献就越小。

排序之后,

第$i$个孩子的饼干只有两种情况:

  1. 饼干数小于第$i-1$个孩子拥有的饼干数,即$a_i=i-1$
  2. 饼干数等于第$i-1$个孩子拥有的饼干数,此时我们要统计在$i$之前有多少个孩子饼干数与$i$相同。

发现很难维护状态,

经过引导,

  1. 若第$i$个孩子获得的饼干数$>1$,则每一个人少拿一块饼干,效果是等价的。
  2. 若饼干数$=1$,就可以上文第二种情况操作,通过枚举来统计。

那么方程就显而易见了,

$F_{i,j}$表示前$i$个人共有$j$块饼干。

$$F_{i,j}=\min\begin{Bmatrix}F_{i,j-1}\\ \min\limits_{0\le k<i}\begin{Bmatrix} F_{k,j-(i-k)}+k*\sum\limits_{p=k+1}^ig_p\end{Bmatrix} \end{Bmatrix}$$

$lyd$太强了!

对了,还要记录饼干数,用两个前继分别记录$i,j$就可以了。

记得对应操作

对应第一种情况

if(pi[n][m]==n)
{
    for(int i=1;i<=n;i++)
        ++ans[a[i].id];
}

对应第二种情况

else
{
    for(int i=pi[n][m]+1;i<=n;i++)
        ans[a[i].id]=1;
}

AC code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
using namespace std;
const int N=31,M=5005;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node{int id,d;bool operator <(const node a)const{return d>a.d;}}a[N];
int sum[N],ans[N];
ll f[N][M];int pi[N][M],pj[N][M];
void calc(int n,int m)
{
    if(!n)return ;
    calc(pi[n][m],pj[n][m]);
    if(pi[n][m]==n)
        for(int i=1;i<=n;i++)
            ans[a[i].id]++;
    else
        for(int i=pi[n][m]+1;i<=n;i++)
            ans[a[i].id]=1;
}
int main()
{
    int n,m;qr(n);qr(m);
    for(int i=1;i<=n;i++)qr(a[i].d),a[i].id=i;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].d;
    memset(f,0x3f,sizeof(f));f[0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(j-i>=0)//每个位置减少1 
            {
                f[i][j]=f[i][j-i];
                pi[i][j]=i;
                pj[i][j]=j-i;
            }
            int p;
            for(int k=0;k<i;k++)
                if(j-(i-k)>=0&&f[k][p=j-(i-k)]+k*(sum[i]-sum[k])<f[i][j])//k+1~i饼干数为1 
                {
                    f[i][j]=f[k][p]+k*(sum[i]-sum[k]);
                    pi[i][j]=k;
                    pj[i][j]=p;
                }
        }
    printf("%lld\n",f[n][m]);
    calc(n,m);
    for(int i=1;i<=n;i++)qw(ans[i]),putchar(' ');
    return 0;
}