MZOJ 1005: 打水 【一道很好的dfs&&完全背包练手题】
MZOJ 1005: 打水
这么富有绵中气息的题目当然要做一做啦
我又想起了发哥开飞机去董家沟买零食
进入正题
思路?一个迭代搜索加一个完全背包套题。和俄罗斯套娃差不多
怎么迭代搜?
定义一个MAXD表示当前搜索树的最大深度,不断增加MAXD的值,相当于去搜全排列。但是不断增加全排列的数字个数。
怎么套完全背包?
将搜出来的全排列跑一边完全背包,然后检查n是否可以被表示出来!WARMING:搜索的时候要把数组开大一点!!!
CODE:
#include <bits/stdc++.h>
using namespace std;
const int maxn=20005;
int c[maxn],n,m,used[maxn],ans[maxn],can[maxn*2];
bool flag;
int maxd=0;
void init()
{
freopen("MZOJ1005.in","r",stdin);
}
void readdata()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d",&c[i]);
}
bool judge()//完全背包
{
memset(can,0,sizeof(can));
for(int i=1;i<=maxd;i++)
{
can[ans[i]]=1;
}
for(int i=1;i<=2*n;i++)//数组开大一点!!!!不然有可能算不出来
{
if(can[n])//剪枝
{
flag=1;return true;
}
if(can[i])//如果他/她能被标识出来
{
for(int j=1;j<=maxd;j++)//那么在他之前的可以被标出来的数加上他本身也可以被表示出来
{
can[i+ans[j]]=1;
}
}
}
if(can[n])
{
flag=1;return true;
}
else return false;
}
void dfs(int x)//迭代搜索
{
if(x==maxd+1)//迭代的方法
{
judge();
return;
}
for(int i=1;i<=m;i++)
{
if(!flag && !used[i])
{
used[i]=1;
ans[x]=c[i];
dfs(x+1);
used[i]=0;
}
}
}
void work()
{
while(flag==false)//迭代神搜
{
memset(used,0,sizeof(used));
memset(ans,0,sizeof(ans));
maxd++;
dfs(1);
}
printf("%d ",maxd);
for(int i=1;i<=maxd;i++)
printf("%d ",ans[i]);
}
int main()
{
init();
readdata();
work();
return 0;
}