• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

P1095 [NOIP2007 普及组] 守望者的逃离 解题报告

开发技术 开发技术 2周前 (04-08) 3次浏览

原题链接

考察:线性dp+贪心

本蒟蒻真真菜到抠脚…二维MLE,滚动后TLE,绝望…已经菜到不会写普及组的题.

错误思路:

       设f[i][j]为i秒时魔力为j的最大距离,总共三种决策:

       一、 休息, f[i][j] = f[i-1][j]

       二、 魔法,f[i]j] = f[i-1][j+10]+60

       三、跑步,f[i][j] = f[i-1][j]+17.

空间108*4 B = 400MB左右,会MLE.

      一开始是想直接压到一维,但是二用到了比j大的状态,只能正序,但是其他要倒序.后来看了讨论提示直接滚动数组…..因为只用到i-1与i的状态.108的复杂度,结果TLE.

正确思路:

       二维错误,那么一定是要压到一维,最需要记录的状态是时间.此时是休息还是跑步需要决策.休息需要2.5s,如果跑步跑3*17 = 51m,效果不如休息…所以能用魔法尽量用魔法.但有一种情况需要用跑步,即休息时间已经够跑出去了或者不能跑出去但能更新最大距离…所以先用魔法休息决策更新最优距离,再用跑步更新最远距离.

 1 #include <iostream>
 2 #include <cstring> 
 3 using namespace std;
 4 const int N = 300010,M = 1010;
 5 int m,s,t,f[N],maxn;
 6 void solve() 
 7 {
 8     f[0] = 0;
 9     int manx = 0;
10     for(int i=1;i<=t;i++)
11     {
12         if(m>=10) f[i] = f[i-1]+60,m-=10;
13         else m+=4,f[i] = f[i-1];
14     }
15     for(int i=1;i<=t;i++) f[i] = max(f[i-1]+17,f[i]);
16     for(int i=1;i<=t;i++)
17       if(f[i]>=s) {printf("Yesn%dn",i); return;}
18       else maxn = max(maxn,f[i]);
19     printf("Non%dn",maxn);
20 }
21 int main()
22 {
23     scanf("%d%d%d",&m,&s,&t);
24     solve();
25     return 0;
26 }

 


程序员灯塔
转载请注明原文链接:P1095 [NOIP2007 普及组] 守望者的逃离 解题报告
喜欢 (0)