题目翻译:让我们回忆一下一个古老的笑话: 曾经有一个绅士对另一个绅士说: — 我们玩牌怎么样? — 你知道吗,我已经十年没玩牌了… — 而我已经十五年没玩了… 于是,他们决定逐渐重温年轻时光。第一个绅士让仆人拿来一副牌,在开始玩之前,他用手称量了一下牌。 — 我觉得这副牌缺了一张牌… — 他说着,把牌递给了另一个绅士。 — 是的,黑桃九, — 那人同意道。 给出了一副不完整的牌。程序应该确定缺了哪些牌。 输入 第一行包含一个正整数,表示给定不完整牌的重量(以毫克为单位)。第二行包含一个整数N,2 ≤ N ≤ 100,表示完整牌的数量。接下来的N行中,包含了1到1000之间的整数,表示每张牌的重量(以毫克为单位)。保证完整牌的总重量严格大于不完整牌的重量。 输出 如果没有解决方案,则输出单个数字0。如果有多个解决方案,则输出-1。最后,如果可以明确确定不完整牌与完整牌相比缺少哪些牌,则按升序输出缺少的牌的编号,用空格分隔。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
const int mod=998244353;
const int maxn=1e5+10;
//main code
int N,W,a[maxn],dp[maxn],sum,pre[maxn];
vector<int> ans;
main(){
cin >> W >> N;
for(int i=1;i<=N;i++){
cin >> a[i];
sum+=a[i];
}
if(sum<W){
cout << 0 << endl;
return 0;
}
W=sum-W;
dp[0]=1;
for(int i=1;i<=N;i++){
for(int j=W;j>=a[i];j--){
if(dp[j-a[i]]){
dp[j]=min((int)2,dp[j]+dp[j-a[i]]);
pre[j]=i;
}
}
}
if(dp[W]==0){
cout << 0 << endl;
return 0;
}else if(dp[W]>1){
cout << -1 << endl;
return 0;
}
for(int i=W;i;i-=a[pre[i]]){
ans.push_back(pre[i]);
}
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++){
cout << ans[i] << " ";
}
return 0;
}
错了第十四个点