[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

样例输入1

Copy

样例输出1

2 3 5

Copy

限制

各个测试点1s

来源

From facer

试题分析：迭代深搜，最后DP背包判断就好了 QAQ

代码：

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#include<stack>

#include<vector>

#include<algorithm>

//#include<cmath>

using namespace std;

const int INF = 9999999;

#define LL long long

inline int read(){

	int x=0,f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*f;

}

int N,M;

bool vis[20001];

int k[201],tmp,K;

int ans[20001];

int p=0;

bool judge(){

	memset(vis,0,sizeof(vis));

	vis[p]=true;

	for(int i=1;i<=K;i++){

		for(int j=p;j<=N;j++)

			if(j-ans[i]>=0&&vis[j-ans[i]]) vis[j]=true;

	}

	return vis[N];

}

void search(int t,int step){

	p+=k[step];

	ans[t]=k[step];

	if(t==K){

		if(judge()){

			printf("%d ",K);

			for(int i=1;i<K;i++)

			    printf("%d ",ans[i]);

			printf("%d\n",ans[K]);

			exit(0);

		}

		p-=k[step];

		return ;

	}

	if(step>=M) return ;

	for(int i=step+1;i<=M;i++) search(t+1,i);

	p-=k[step];

}

int main(){

	//freopen(".in","r",stdin);

	//freopen(".out","w",stdout);

	N=read(),M=read();

	for(int i=1;i<=M;i++) k[i]=read();

	sort(k+1,k+1+M);

	for(int i=1;i<=M;i++)

	    for(int j=1;j<=M-i+1;j++){

		    K=i;search(1,j);

    	}

	return 0;

}

巴特西

【DFS】【DP】岳麓山上打水

[vijos1159]岳麓山上打水

描述

格式

输入格式

输出格式

样例1

样例输入1

样例输出1

限制

来源

最新文章

热门文章