比赛 NOIP2008集训模拟2 评测结果 WTATTTTTTT
题目名称 美酒节赛羊 最终得分 10
用户昵称 zqzas 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2008-11-11 11:23:44
显示代码纯文本
#include <iostream>

#define INF 99999999

using namespace std;

int t,s,p,a,b,c;

void dfs(int dis,int tired,int now)
{
	if (dis>=s)
	{
		if (now<=t)
			t=now;
		return;
	}
	if (now>=t)
		return;
	//take rest
	if (tired==p)
	{
		if (p>10)
			dfs(dis+10,tired-10,now+10);
		else
			dfs(dis+10,0,now+10);
	}
	else
		if (tired-1>=0)
			dfs(dis+1,tired-1,now+1);
	//go in speed 1
	if (tired+2<=p)
	{
		dfs(dis+5,tired+2,now+1);
	}
	//go in speed 2
	if (tired+5<=p)
		dfs(dis+10,tired+5,now+1);
}


void run1()
{
	t=INF;
	dfs(0,0,0);
}

void run2()
{
	t=999999999;
	for (c=0;c<=s;c++)
		for (b=0;b<=s;b++)
		{
			if (7*b+15*c>=s && 7*b+15*c<=s+4)
				if (3*b+6*c<=t)
					t=3*b+6*c;
		}
}

void ini()
{
	cin>>s>>p;
}

int main()
{
	freopen("goat.in","r",stdin);
	freopen("goat.out","w",stdout);
	ini();
	if (s>=200000)
	   run2();
    else
       run1();
	cout<<t;
	return 0;
}