题解 | #叠硬币#

题意

对于n个硬币堆，如果想选取一些硬币堆，一堆一堆地叠起来，将它们叠到正好H个硬币那样高（不可以随意增加或减少每个硬币堆的硬币数量），最少需要几个硬币堆。可以堆成则输出方案，不行输出-1.

思路

如果只是单纯的求需要几个硬币堆，很容易写DP，但是这个题还要把方案也一并输出。我们可以额外的再开一个数组记录，记录的是构成高度为j但除了当前这一堆硬币，其他硬币的总高度。求方案的时候在用 j-f[i][j] 求到的就是选择当前这堆硬币，硬币的高度。

递推方程也很容易写：

dp[i][j]=min(dp[i][j],dp[i-1][j-a[i]]+1);

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
const int MOD = 998244353;
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int a[N],n,H;

int dp[3010][3010];//这个记录答案
int f[3010][3010];//记录的是除了当前这一堆硬币，其他硬币的高度
//dp[i][j]表示从前i个选高度正好为H的最少堆数
//dp[i][j]=min(dp[i][j],dp[i-1][j-a[i]]+1);
void solve(){
	cin>>n>>H;
	for(int i=1;i<=n;i++){
        cin>>a[i];
    }sort(a+1,a+n+1);
    for(int i=0;i<=n;i++){
        for(int j=0;j<=3000;j++){
            dp[i][j]=-1;
        }
    }
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        dp[i][a[i]]=1;
        dp[i][0]=0;
        for(int j=1;j<=H;j++){
            dp[i][j]=dp[i-1][j];
            f[i][j]=j;
        }
        for(int j=a[i];j<=H;j++){
            if(dp[i-1][j-a[i]]>=0&&(dp[i][j]==-1||dp[i][j]>=dp[i-1][j-a[i]]+1)){
                dp[i][j]=dp[i-1][j-a[i]]+1;
                f[i][j]=j-a[i];
            }
        }
    }
    if(dp[n][H]==-1){
        cout<<-1<<endl;
        return;
    }
    vector<int> ans;
    for(int i=n,j=H;i>=1;i--){
        if(j-f[i][j]) ans.push_back(j-f[i][j]);
        j=f[i][j];
    }
    reverse(ans.begin(), ans.end());
    cout<<ans.size()<<endl;
    for(auto&t:ans){
        cout<<t<<" ";
    }
    cout<<endl;
}

signed main(){
	int _=1;
	//cin>>_;
	while(_--) solve();
	return 0;
}