usaco_5_3_1_milk4.cpp

usaco自己做的1到5章的代码

/*
PROB: milk4
LANG: C++
*/
/*
dfsid+dp
时间压1s过的，所以不多说了……
这道题要用到迭代加深搜索(DFSID)。由于要求输出的是使用最少的牛奶桶，所以要先找牛奶桶数量为1的时候所有的组合，如果没有解再找牛奶桶数量为2...直到牛奶桶数量为P。
当搜索到一个组合，判断用这些牛奶桶是否能组成目标解的时候，可以用动态规划的方法来做。设f[i]是当需求的牛奶为i时，能否形成这个组合，是一个布尔型数组。
初始条件 f[0]=true
状态转移方程 f[i]=f[i] or f[ i-v[j] ] (j为使用的所有牛奶桶)
目标状态 f[Q]
如果f[Q]为true，则当前解合法，直接输出即可。
但是如果仅仅这样写还是有一组数据过不去，需要进行一些优化。要优化动态规划的过程。
注意一个重要的信息，找到的组合中，每个牛奶桶至少用了一次。上面的状态转移方程中有许多某个牛奶桶使用0次的冗余状态。可以在初始的时候对(i=1..Q/v[第一个桶]) f[ i*v[第一个桶] ]赋值为true。对每个其他的桶的状态可以直接由前面的状态得出。
经过这个优化，数据就可以全过了。
*/
#include<iostream>
#include<fstream>
#include<memory>
#include<cmath>
#include<algorithm>
#include<iomanip>
//#define cin fin
using namespace std;
int puse[102],v[102];
bool reach[20005];
int ans,n,p,q;
 void printans()
{
	ofstream fout("milk4.out");
	fout<<ans;
	for (int i=1;i<=ans;i++)
	    fout<<' '<<v[puse[i]];
	fout<<endl;
}
void dp()
{
	int i,j;
	memset(reach,false,sizeof(reach));
	/*for(i=1;i<=ans;i++) reach[v[puse[i]]]=true;
	for(j=1;j<=ans;j++)
		for (i=1;i<=q;i++)
		{
			if(reach[i] || (reach[i-v[puse[j]]] && i-v[puse[j]]>=0)) reach[i]=true;
		}
		*/ //上面注释部分是我自己的dp部分，刚好压着1秒过的，下面的dp部分是网上题解的做法，最慢只要0.18s。
    for (i=1;i<=q/v[puse[1]];i++)
        reach[ i*v[puse[1]] ]=true;
    for (i=2;i<=ans;i++)
        for (j=v[puse[i]];j<=q;j++) //第一种牛奶桶至少用了一次
            reach[j] |= reach[ j- v[puse[i]] ] ;
	if( reach[q] ) {printans(); exit(0);}
}

void dfs(int dep)
{

	for(int i=puse[dep-1]+1;i<=p-ans+dep;i++)
	{
            puse[dep]=i;
            if(dep==ans) dp();
	        	else dfs(dep+1);
	}
}
void dfsid()
{
	for(int i=1;i<=p;i++){
		ans=i;
		dfs(1);
	}
}
int main()
{
	ifstream fin("milk4.in");
    int i,j,k,des;
	fin>>q>>p;
	for(i=1;i<=p;i++)
		fin>>v[i];
	sort(v,v+p);
	memset(puse,0,sizeof(puse));
	dfsid();
    return 0;
}