「vijos1159」岳麓山上打水
描述
今天天气好晴朗，处处好风光，好风光！蝴蝶儿忙啊，蜜蜂也忙，信息组的同学们更加忙。最近，由于XX原因，大家不得不到岳麓山去提水。55555555~，好累啊。 信息组有一个容量为q升的大缸，由于大家都很自觉，不愿意浪费水，所以每次都会刚好把缸盛满。但是，信息组并没有桶子（或者瓢）来舀水，作为组内的生活委员，你必须肩负重任，到新一佳去买桶子。 新一佳有p种桶子，每种桶子都有无穷多个^_^，且价钱一样。由于大家都很节约，所以你必须尽量少买桶子。如果有多种方案，你必须选择“更小”的那种方案，即：把这两个方案的集合（不同大小的桶子组成）按升序排序，比较第一个桶，选择第一个桶容积较小的一个。如果第一个桶相同，比较第二个桶，也按上面的方法选择。否则继续这样的比较，直到相比较的两个桶不一致为止。例如，集合{3，5，7，三} 比集合 {3，6，7，8} 要好。 为了把缸装满水，大家可以先从岳麓山的井里把桶装满水提回来，然后倒进缸里。为了不十分麻烦或者浪费宝贵的水资源，大家决不把缸里的水倒出来或者把桶里的水倒掉，也不会把桶里的水再倒回井中，（这样会污染井水）。当然，一个桶可以使用多次。例如，用一个容积为 1 升的桶可以将任意容量的大缸装满水。而其它的组合就要麻烦些。
输入格式
第1行1个数q(q<=20000)。 第2行1个数p(p<=100)。 接下来p行，每行一个数，依次为每个桶的容积。
输出格式
共1行，每两个数间用空格分隔，第1个数k为最少的桶的数量，接下来k个数从小到大输出每个桶的容量。
样例输入
样例输出
代码
|
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 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<iostream> #include<algorithm> #include<cstring> using namespace std; int a[101],used[101]; int k,s=0; bool ans=0,f[20001]; int mv,p; bool dp() { memset(f,0,sizeof(f)); f[s]=1; for(int i=1;i<=k;i++) for(int v=s;v<=mv;v++) if(v-used[i]>=0&&f[v-used[i]])f[v]=1; if(f[mv]) { cout<<k<<' '; for(int j=1;j<=k;j++) cout<<used[j]<<' '; return 1; } return 0; } void search(int x,int y) { if(ans)return; s+=a[y]; used[x]=a[y]; if(x==k) { if(dp())ans=1; } else for(int i=y+1;i<=p;i++) search(x+1,i); s-=a[y]; } int main() { cin>>mv>>p; for(int i=1;i<=p;i++) cin>>a[i]; sort(a+1,a+p+1); for(k=1;k<=p;k++) for(int i=1;i<=p-k+1;i++) { search(1,i); if(ans)return 0; } } |
Subscribe
计数器 9774150
OI 课件=>
OI 课件=>