【题目大意】

把$m$块饼干分给$n$个孩子，第i个孩子有一个贪婪度$g_i$，如果有$a_i$个孩子获得的饼干比第i个孩子多，那么这个孩子就会产生$g_i*a_i$的怨气值。求一种方案，保证每个孩子至少有一块饼干，并且使所有孩子的怨气值总和最小。

【思路解析】

 首先我们把孩子按照怨气值从大到小排序，那么他们所分到的饼干一定是单调递减的。设$f[i][j]$表示前$i$个孩子一共分到$j$块饼干时，这些孩子的怨气值之和的最小值。再考虑转移方程，有两种情况：

1.第$i+1$个孩子获得的饼干数比第$i$个孩子少，此时$a[i+1]=i$

2.第$i+1$个孩子获得的饼干数与第$i$个孩子相同，此时还需要知道$i$前面有几个孩子与$i$获得的饼干数也相同，才能计算出$a[i+1]$

因为在现有的DP状态下，我们很难高效地维护这些信息，所以我们不妨对状态转移做一个等价转换。

1.若第$i$个孩子获得的饼干数大于1，则等价与分配$j-i$个饼干给前$i$个孩子，也就是每人少拿一块饼干，获得的饼干数的相对大小顺序不变，从而怨气值之和也不变。

2.若第$i$个孩子获得的饼干数为1，则枚举前面有多少个孩子也获得一块饼干。

于是整个DP算法的状态转移方程为：

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

初始值：$f[0][0]=0$

目标：$f[n][m]$

这道题启发我们，有时可以通过额外的算法确定DP状态的计算顺序，有时可以在状态空间中运用等效手法进行缩放。

【代码实现】

1 #include
      
        2 #define rg register 3 #define go(i,a,b) for(rg int i=a;i<=b;i++) 4 using namespace std; 5 const int N=32,M=5002; 6 const int INF=1e9+7; 7 int n,m; 8 struct qi{ 9     int num,id;10 }g[N];11 struct ans{12     int i,j;13 }a[N][M];14 int f[N][M],as[N];15 bool cmp(qi a,qi b){
    return a.num>b.num;}16 int main(){17     scanf("%d%d",&n,&m);18     go(i,1,n) scanf("%d",&g[i].num),g[i].id=i;19     go(i,0,n) go(j,0,m) f[i][j]=INF;f[0][0]=0;20     sort(g+1,g+1+n,cmp);21     go(i,2,n) g[i].num+=g[i-1].num;22     go(i,1,n) go(j,i,m){23         f[i][j]=f[i][j-i];a[i][j]=(ans){i,j-i};24         go(k,0,i-1)25             if(f[i][j]>f[k][j-(i-k)]+k*(g[i].num-g[k].num))26                 f[i][j]=f[k][j-(i-k)]+k*(g[i].num-g[k].num),a[i][j]=(ans){k,j-(i-k)};27     }28     int t1=n,t2=m;29     while(t1){30         if(t1==a[t1][t2].i){go(i,1,t1) as[g[i].id]++;}31         else{go(i,a[t1][t2].i+1,t1)as[g[i].id]++;}32         int tt=t1;t1=a[t1][t2].i;t2=a[tt][t2].j;33     }34     printf("%d\n",f[n][m]);35     go(i,1,n) printf("%d ",as[i]);36     return 0;37 }