饼干

挺有价值的一个dp,记录一下..

//先分配最大的,然后枚举几个1dp即可
#include <bits/stdc++.h>
using namespace std;
const int N=5e3+5,M=35;
int f[M][N];//
int sum[N];

struct vv{
    int id,val;
}a[N];

bool cmp(vv x,vv y)
{
    if(x.val==y.val) return x.id<y.id;
    else             return x.val>y.val;
}

int ans[M];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].val);
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)   sum[i]+=sum[i-1]+a[i].val;
    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) f[i][j]=f[i][j-i];
            for(int k=1;k<=i&&k<=j;k++)
            {
                f[i][j]=min(f[i][j],f[i-k][j-k]+(sum[i]-sum[i-k])*(i-k));
            }
        }
    }
    cout<<f[n][m]<<endl;
    int cnt=n;
    int h=0;
    while(n&&m)
    {
        if(m>=n&&f[n][m]==f[n][m-n])    m-=n,h++;
        else
        {
            for(int k=1;k<=n&&k<=m;k++)
            {
                if(f[n][m]==f[n-k][m-k]+(sum[n]-sum[n-k])*(n-k))
                {
                    for(int i=n;i>=n-k+1;i--)
                    ans[a[i].id]=h+1;
                    n-=k,m-=k;
                    break;
                }
            }
        }
    }
    for(int i=1;i<=cnt;i++)
    cout<<ans[i]<<' ';
    cout<<endl;
    return 0;
}