「vijos1071」新年趣事之打牌
描述
过年的时候，大人们最喜欢的活动，就是打牌了。xiaomengxian不会打牌，只好坐在一边看着。
这天，正当一群人打牌打得起劲的时候，突然有人喊道：“这副牌少了几张！”众人一数，果然是少了。于是这副牌的主人得意地说：“这是一幅特制的牌，我知道整副牌每一张的重量。只要我们称一下剩下的牌的总重量，就能知道少了哪些牌了。”大家都觉得这个办法不错，于是称出剩下的牌的总重量，开始计算少了哪些牌。由于数据量比较大，过了不久，大家都算得头晕了。
这时，xiaomengxian大声说：“你们看我的吧！”于是他拿出笔记本电脑，编出了一个程序，很快就把缺少的牌找了出来。
如果是你遇到了这样的情况呢？你能办到同样的事情吗？
输入格式
第一行一个整数TotalW，表示剩下的牌的总重量。
第二行一个整数N（1<N<=100），表示这副牌有多少张。
接下来N行，每行一个整数Wi（1<=Wi<=1000），表示每一张牌的重量。
输出格式
如果无解，则输出“0”；如果有多解，则输出“-1”；否则，按照升序输出丢失的牌的编号，相邻两个数之间用一个空格隔开。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include<iostream> using namespace std; int n; int w[101],f[100001],used[101],father[100001]; int mw; int main() { f[0]=1; cin>>mw>>n; for(int i=1;i<=n;i++) cin>>w[i]; if(mw==0) { for(int i=1;i<=n;i++) cout<<i<<' '; return 0; } for(int i=1;i<=n;i++) for(int v=mw;v>=w[i];v--) { if(f[v-w[i]]) { if(f[v]==0){f[v]=1;father[v]=i;} else f[v]=-1; } else if(f[v-w[i]]==-1)f[v]=-1; } if(!f[mw]||f[mw]==-1){cout<<f[mw];return 0;} int s=mw; while(s!=0) { used[father[s]]=1; s=s-w[father[s]]; } for(int i=1;i<=n;i++) if(!used[i])cout<<i<<' '; return 0; } |
Subscribe
计数器 9786894
OI 课件=>
OI 课件=>