C++ 解法, 执行用时: 220ms, 内存消耗: 18040K, 提交时间: 2022-01-20 23:47:12

#include<bits/stdc++.h>
using namespace std;
int a[50];
int dp[50][30*5001];
int ny[5005];
int yy[50];
int main()
{
    int n;
    cin>>n;
 ;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
  
    for(int i=0;i<=5001;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i>a[j]) ny[i]++;
        }
    }
    int num=0;
    yy[0]=0;
  
    for(int i=1;i<=5001;i++)
    {
        if(ny[i]!=ny[i-1]) yy[++num]=i;
        
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=sum;j++)
        {
            for(int k=0;k<=num&&yy[k]<=j;k++)
            {
                int z=ny[yy[k]];
               if(j-yy[k]<0) break;
                dp[i][j]=max(dp[i-1][j-yy[k]]+z,dp[i][j]);
            }
        }
    }
    int s=0;
    //cout<<dp[n][sum]<<endl;
    //cout<<dp[n-1][sum-1]<<endl;
    for(int i=1;i<=n;i++)
    {
        if(i==n) {cout<<sum-s<<endl;break;}
        for(int k=0;k<=num&&yy[k]<=sum-s;k++)
        {
           
           int z=ny[yy[k]];
   
          if(dp[n-i+1][sum-s]==dp[n-i][sum-s-yy[k]]+z)
          {
              cout<<yy[k]<<" ";
              s+=yy[k];
              break;
          }
        }
    }
   
  
}