哇,好像是到目前为止为数不多的几次独立思考并没看题解而写出的dp……

美中不足的是,最后好像忘记初始化状态了……

题目描述

恶魔猎手尤迪安野心勃勃,他背叛了暗夜精灵,率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀,被困在一个荒芜的大岛上。为了杀死守望者,尤迪安开始对这个荒岛施咒,这座岛很快就会沉下去。到那时,岛上的所有人都会遇难。守望者的跑步速度为17m/s,以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术,可在1s内移动60m,不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s,只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值M,他所在的初始位置与岛的出口之间的距离S,岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛,若不能逃出,则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位,且每次活动的持续时间为整数秒。距离的单位为米(m)。

输入输出格式

输入格式:

输入文件escape.in仅一行,包括空格隔开的三个非负整数M, S, T。

输出格式:

输出文件escape.out包含两行:

第1行为字符串“Yes”或“No”(区分大小写),即守望者是否能逃离荒岛。

第2行包含一个整数。第一行为“Yes”(区分大小写)时表示守望者逃离荒岛的最短时间;第一行为“No”(区分大小写)时表示守望者能走的最远距离。

我们来看一下,显然要用时间作为状态(因为路程太大而不好转移)而状态必须是二维的(考虑到法术值对决策的影响)

输出了一下sizeof(f[300010][1010])/1024/1024,发现有一个G,怎么办呢?

考虑一个贪心思想,不用白不用啊……

于是就可以设计状态了。我一开始居然想直接f[300010]转移……写着写着发现没法转移。

f[i][j]表示前i秒j个ep最远距离,顺便Notepad++万岁

 

手推一下样例,

exp1
39 200 4
180m 9ep -> 前3s
180m 13ep -> 第4s / 197m 9ep -> 第4s
died.

exp2
36 255 10
180m 6ep -> 前3s
180m 10ep -> 第4s
240m 0ep -> 第5s
257m 0ep -> 第6s

Yes-6s

试着写写方程,写到一半突然相当初始m会很大的问题……于是有了这个……

	while (m>=10)
	{
		f[++c1][0]=f[c1-1][0]+60;
		m-=10;
		if (f[c1][0]>=s && c1<=t)
		{
			printf("Yes\n%d\n",c1);
			return 0;
		}
		else if (c1>t)
		{
			printf("No\n%d\n",t*60);
			return 0;
		}
	}

c1是计数器。

然后试着写写方程,转移一发

for (int i=c1;i<=t;i++)
		for (int j=0;j<=20;j++)
		{
			if (j<10) f[i][j]=max(f[i-1][j]+17,f[i-1][j+10]+60);//Silly Walk
			else f[i][j]=f[i-1][j]+17;
			if (j>=4) f[i][j]=max(f[i][j],f[i-1][j-4]); //Recover
			
			if (f[i][j]>=s)
			{
				printf("Yes\n%d\n",i);
				return 0;
			}
		}

为什么要j<=20呢?显然j>10的时候必须直接+17,+60并耗魔法一定不会影响决策……因为不用白不用,用了一定节省时间,所以最优解一定在[0,10)区间里取,f[i][j] (j>=10)再从f[i-1][j+10]转移就没意义了,所以j上限应该是19,手癌就打了个20.

最后别忘记更新一波初始状态,还是注意j<=20

if (c1>0) 
	{
		f[c1-1][m+10]=f[c1][0]-60;
		f[c1-1][0]=f[c1][0]=0;
	}
	else 
	{
		c1=1;
		for (int j=m+1;j<=20;j++) f[0][j]=-1e9;
	}

所以这里是全部的代码,注意最后出解j并不影响,所以找到一个直接return 0

但是无解j会影响,显然j<10更优,不用白不用嘛

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<iterator>
#include<utility>
using namespace std;

int m,s,t;
int f[300010][50]={0},c1=0;

int main()
{
	scanf("%d%d%d",&m,&s,&t);
	
	while (m>=10)
	{
		f[++c1][0]=f[c1-1][0]+60;
		m-=10;
		if (f[c1][0]>=s && c1<=t)
		{
			printf("Yes\n%d\n",c1);
			return 0;
		}
		else if (c1>t)
		{
			printf("No\n%d\n",t*60);
			return 0;
		}
	}

	if (c1>0) 
	{
		f[c1-1][m+10]=f[c1][0]-60;
		f[c1-1][0]=f[c1][0]=0;
	}
	else 
	{
		c1=1;
		for (int j=m+1;j<=20;j++) f[0][j]=-1e9;
	}
	
	for (int i=c1;i<=t;i++)
		for (int j=0;j<=20;j++)
		{
			if (j<10) f[i][j]=max(f[i-1][j]+17,f[i-1][j+10]+60);//Silly Walk
			else f[i][j]=f[i-1][j]+17;
			if (j>=4) f[i][j]=max(f[i][j],f[i-1][j-4]); //Recover

			if (f[i][j]>=s)
			{
				printf("Yes\n%d\n",i);
				return 0;
			}
		}
	
	for (int i=0;i<=9;i++) f[t][0]=max(f[t][0],f[t][i]);
	printf("No\n%d\n",f[t][0]);
	return 0;
}

 

分类: DP贪心

发表评论

电子邮件地址不会被公开。 必填项已用*标注