Home > Old Blog Posts > USACO 5.3.1 Milk Measuring

USACO 5.3.1 Milk Measuring


这题我采取了IDDFS+背包判断的方法,有关IDDFS的讲述请参阅
http://ace.delos.com/usacotext2?a=Uehl1G0ncBb&S=rec
USACO上关于IDDFS的讲述已经很详细了
Nocow上有此题的纯DP算法,暂不赘述,如有兴趣请见http://www.nocow.cn/index.php/USACO/milk4

/*
ID: dementr1
PROG: milk4
LANG: C++
*/
#include
#include
using namespace std;
ifstream fin ("milk4.in");
ofstream fout ("milk4.out");
int p=0, v[100]={},q;
bool f[20001]={false},vis[20001]={false};
bool solved=false;
int length;
bool used[100]={false};
int list[100]={};
void init()
{
	int tmpp=0,tmpv[100]={};
	fin>>q>>tmpp;
	for(int i=0;i>tmpv[i];
	fin.close();
	bool dontchoose[100]={false};
	for(int i=0;iv[i])
			{
				for(int k=i;k>j;k--)
					v[k]=v[k-1];
				v[j]=tmp;
				break;
			}
	}
}
void dp(int now)
{
	for(int i=0;i
=0)
			{
				if(!vis[now-v[i]])
					dp(now-v[i]);
				if(f[now-v[i]])
				{
					f[now]=true;
					break;
				}
			}
	vis[now]=true;
	return;
}
void dfs(int deep, int id)
{
	if(solved)
		return;
	if(deep==id)
	{
		for(int i=0;i<=q;i++)
		{
			f[i]=false;
			vis[i]=false;
		}
		f[0]=true;
		dp(q);
		if(f[q])
		{
			fout<<<" ";
			for(int i=0;i<<<" ";
			fout<<0)
		start=list[deep-1]+1;
	for(int i=start;i
Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: