C++(g++ 7.5.0) 解法, 执行用时: 6ms, 内存消耗: 1576K, 提交时间: 2022-08-10 14:15:05

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=35,M=5005;
int f[N][M],n,m,ans[N],b[N][M];
PII a[N];
int main()
{
    cin>>n>>m;
    memset(f,0x3f,sizeof f);
    for(int i=1; i<=n; i++)
        cin>>a[i].first, a[i].second=i;
    sort(a+1,a+1+n,greater<PII>());
    for(int i=1; i<=n; i++)
        a[i].first+=a[i-1].first, f[i][0]=0;
    for(int i=1; i<=n; i++)
        for(int j=i; j<=m; j++) {
            f[i][j]=f[i][j-i];
            b[i][j]=n+1;
            for(int k=0; k<i; k++) {
                int s=f[k][j-i+k]+k*(a[i].first-a[k].first);
                if(f[i][j]<=s)continue;
                f[i][j]=s;
                b[i][j]=k;
            }
        }
    cout<<f[n][m]<<endl;
    int i=n, j=m, h=0;
    while(i)
    {
        int k=b[i][j];
        for(int u=i; u>k; u--)
            ans[a[u].second]=(k ? h+1 : h);
        if(k<=n) j-=i-k, i=k;
        else if(j>=i)
            j-=i, h++;
    }
    for(i=1;i<=n;i++)cout<<ans[i]<<" ";
    cout << endl;
}

C++14(g++5.4) 解法, 执行用时: 8ms, 内存消耗: 2424K, 提交时间: 2020-08-05 15:49:12

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=50,M=5e3+10;
int f[N][M],g[N],id[N],sum[N],cnt[N][M],hav[N][M],ans[N];
int cmp(const int &a,const int &b){return g[a]>g[b];}
void print(int n,int m)
{
	if(!n)return;
	print(cnt[n][m],hav[n][m]);
	if(cnt[n][m]==n)for(int i=1;i<=n;i++)ans[id[i]]++;
	else for(int i=cnt[n][m]+1;i<=n;i++)ans[id[i]]=1;
}
int main()
{
    int n,m;
	scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&g[i]),id[i]=i;
    sort(id+1,id+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[id[i]];
		for(int j=i;j<=m;j++)
	    {
	    	f[i][j]=f[i][j-i];cnt[i][j]=i;hav[i][j]=j-i;
	    	for(int k=0;k<i;k++)
	    	    if(f[i][j]>f[k][j-(i-k)]+(sum[i]-sum[k])*k)
	    	    {
	    	    	f[i][j]=f[k][j-(i-k)]+(sum[i]-sum[k])*k;
	    	    	cnt[i][j]=k;hav[i][j]=j-(i-k);
				}
		}
	}
	printf("%d\n",f[n][m]);
	print(n,m);
	for(int i=1;i<=n;i++)printf("%d%c",ans[i],i==n?'\n':' ');
	return 0;
}

C++ 解法, 执行用时: 10ms, 内存消耗: 3596K, 提交时间: 2022-01-10 09:16:31

#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,k,f[101][5001],s[101],g[101],a[101][5001],b[101][5001],ans[5001],c[101];
int cmp(int a,int b){return g[a]>g[b];}
void print(int n,int m){
	if(!n)return;
	print(a[n][m],b[n][m]);
	if(a[n][m]==n)for(int i=1;i<=n;i++)ans[c[i]]++;
	else for(int i=a[n][m]+1;i<=n;i++)ans[c[i]]=1;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>g[i],c[i]=i;
    sort(c+1,c+1+n,cmp);
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;i++){
		s[i]=s[i-1]+g[c[i]];
		for(int j=i;j<=m;j++){
			f[i][j]=f[i][j-i];
			a[i][j]=i;
			b[i][j]=j-i;
			for(int k=0;k<i;k++)if (f[i][j]>f[k][j-(i-k)]+(s[i]-s[k+1-1])*k){
				f[i][j]=f[k][j-(i-k)]+(s[i]-s[k+1-1])*k;
				a[i][j]=k;
				b[i][j]=j-(i-k);
			}
		}
	}
	cout<<f[n][m]<<"\n";
    print(n,m);
	for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
    return 0;
}