守望者的逃离 （C++代码）

解题思路:





注意事项:





参考代码:

根据题意，守望者要在最短时间走最多的路程，而每秒有三种决策

我们不妨将跑步和使用闪烁法术分开处理

上代码

#include <cstdio>#include <algorithm>using namespace std;int dp[300001];int main(){    int m,s,t;    scanf("%d%d%d",&m,&s,&t);    for(int i=1;i<=t;i++){//处理闪烁法术
       if(m>=10)dp[i]=dp[i-1]+60,m-=10;//如果能用，就用
       else dp[i]=dp[i-1],m+=4;//否则休息
   }    for(int i=1;i<=t;i++){dp[i]=max(dp[i],dp[i-1]+17);//处理跑步，dp[i]为使用法术和跑步的最大值（最优）
   if(dp[i]>=s){printf("Yes\n%d",i);return 0;}//如果超过了距离s，就成功了，输出yes
   }printf("No\n%d",dp[t]);//没成功，输出no
   return 0;
}

评论

题解不要这么暴力啊! 你个膜鬼

评论

题解里为什么那么多dalao用DP,

还是基于时间轴的DP,

这明明是一道,

普(xiao)及(xue)的贪(shu)心(xue)题.

其实这道题贪心模拟比DP快了不少.

首先,我们可算出两种情况的速度:

V(magic)=(4*5/10*60)/(5+2)=120/7;

V(walk)=17=119/17;

因为V(magic)>V(walk),

所以尽可能多地用极限闪避闪现.

因为消耗和增加的膜法都是偶数,

所以得到的膜法^1处理,

我是与膜法有关的都>>1处理.

刚开始一直闪现,

直到把膜法用光.

膜法若有剩余补齐到10的倍数,

继续闪现%%%.

到了最后,

剩下的路程<120或剩下的时间<7,

无法满足两轮一轮蓄力闪现二连,

就walk.

过程中不断特判,

满足条件就立刻输出然后exit(0).

#include<iomanip>#include<cmath>#include<cstdio> #include<cstring> #include<cstdlib>#include<ctime>#include<algorithm>#include<bitset>#include<vector>using namespace std;inline int intin(){register char c=getchar();while(c<48||c>57)c=getchar();register int a=0;while(c>47&&c<58){a=(a<<1)+(a<<3)+c-48;c=getchar();}return a;}inline void intot(int a){if(a>9)intot(a/10);putchar(a%10+48);}int al=0,at=0,magic,sm,tmd;inline void tot(bool b,int k){if(b){putchar(89);putchar(101);putchar(115);}else{putchar(78);putchar(111);}putchar(10);intot(k);exit(0);}//输出  inline void q0t(){if(at==tmd)tot(0,al);}//判断是否超时 inline void q0v(){if(al>=sm)tot(1,at);}//判断是否超距 inline void q1v(){if(sm-al<=17)if(at+1>tmd)tot(0,al);else tot(1,at+1);}//前期膜法补齐时特判 inline void q2v(){if(sm-al<=34)if(at+2>tmd)tot(0,al+17);else tot(1,at+2);}//前期膜法补齐到时特判 int main(){
   magic=intin()>>1;sm=intin();tmd=intin();
   q0v();q0t();//先判断是否有X 0 0之类的奇葩数据
   while(magic>=5)//不断消耗膜法闪现
   {
       q0t();
       al+=60;
       at++;
       q0v();
       magic-=5;
   }
   q0t();q1v();    if(magic)//膜法补齐第一次
   {        if(magic>=3)
       {
           magic-=3;al+=60;at+=2;            if(at>tmd)tot(0,al-60+17);
       }        else
       {
           q2v();
           magic-=1;al+=60;at+=3;            if(at-1>tmd)tot(0,al-60+17);            if(at>tmd)tot(0,al-60+34);
       }
   }
   q0v();q0t();q1v();    if(magic)//膜法补齐第二次
   {        if(magic==3)
       {
           al+=60;at+=2;            if(at>tmd)tot(0,al-60+17);
       }        else
       {
           q2v();
           al+=60;at+=3;            if(at-1>tmd)tot(0,al-60+17);            if(at>tmd)tot(0,al-60+34);
       }
   }
   q0v();q0t();q1v();    while(sm-al>=120&&tmd-at>=7)//不断蓄力闪现素质二连
   {
       at+=7;al+=120;
   }    while(sm>al)//不蓄力了 改为walk
   {
       q0v();q0t();
       al+=17;at++;
   }
   q0v();q0t();//别落了最后再判断一下
   return 0;
}

评论

还没有评论

评论

个人认为这是贪心，dp不用

∵闪比走要快

∴奉行这三个原则：

1.能闪就闪

2.当离终点近或时间要到时，跑

3.否则停下来回复法力

var
m,s,t,ss,tt:longint;
// t代表剩下的时间，s代表剩下的路程，tt代表总时间，ss代表总路程
begin
readln(m,s,t);
ss:=s; tt:=t;
while (s>0) {没逃出去} and (t>0) {岛没沉} do
 begin
  if m>=10 then//能闪，可以预处理
   begin
    dec(m,10);//法力-10
    dec(s,60);//路程-60
    dec(t);//时间-1
    continue;//跳过接下来的步骤
   end;
  if (m+t*4<10) {到岛沉法力也回复不到10} or (trunc(s/17)+1<(10-m)/4+2) {法力恢复好时用跑可以跑出去} then
   begin
    repeat
     dec(t);//时间-1
     dec(s,17);//路程-17
    until (s<=0){跑出去} or (t<=0){岛沉};
    break;//while (s>0) and (t>0)
   end;
  inc(m,4);//恢复法力
  dec(t);//时间-1
 end;//while (s>0) and (t>0)

if s<=0 then//跑出去
 begin
  writeln('Yes');
  writeln(tt-t);
 end
 else//没跑出去
 begin
  writeln('No');
  writeln(ss-s);
 end;
end.

评论

还没有评论

评论

状态前面那么多题解已经讲过了, 我就不细讲了

d(t,m)表示时间为t，有m蓝时的最远距离

重要的是用要用贪心优化dp

如果一开始的蓝大于10的话, 那么就一直闪现, 因为闪现比走路快

这样处理完后, 后面的dp时蓝不会大于20, 因为如果可以闪现时直接闪现不会比原地回蓝更差

下面是代码

#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int Mt(300005); //时间上限const int Mm(1005); //蓝量上限int d[2][Mm]; //使用滚动数组节省空间int main(){    int m,s,T;    cin >> m >> s >> T;    int t(1); //时间
   memset(d,0xc0,sizeof d); //初始化d为极小值
   d[0][m] = 0; //当时间为0，蓝为初始值时距离为0
   int Max(0); //最大距离
   while(t<=T && m>10) //当蓝大于10时一直闪现, 有可能即使一直闪现也跑不出岛屿
   {
       m-=10;
       d[t%2][m] = 60*t;
       Max = max(Max,d[t%2][m]); //当前时间最大距离
       if(Max>=s)    break; //如果已经跑出岛屿
       ++t;
   }    if(Max<s) //如果蓝小于10时未跑出岛屿
   {        for(;t<=T;++t)
       {            for(int p(0);p<20;++p)
           {
               d[t%2][p] = d[(t-1)%2][p]+17; //走路
               if(p<10)    d[t%2][p] = max(d[t%2][p],d[(t-1)%2][p+10]+60); //闪现
               if(p>=4)    d[t%2][p] = max(d[t%2][p],d[(t-1)%2][p-4]); //原地回蓝
               Max = max(Max,d[t%2][p]);
           }            if(Max>=s)    break; //如果跑出岛屿
       }
   }    if(Max>=s)    cout << "Yes" << endl << t;    else        cout << "No" << endl << Max;    return 0;
}

评论

还没有评论

评论

本人蒟蒻，最近刚刚接触dp，思想比较“”单纯“”，但也许更容易给别人讲懂也说不定

思路：

之前就做过十几次dp，思路还很慢，本来一开始想用个三维数组，但看了数据范围就绝望了。之后决定用时间做状态（一个一个试，发现用时间做状态时间最好想）

一共有三个决策：回蓝，闪现，跑步 然后我在这里想了半天，我已经绝望了，但最后灵光一现，把决策分开！！！

分成回蓝，闪现一部分和跑步一部分

因为闪现的平均速度为120/5=24>17 所以按理来说技能是要比跑步快的，但问题是技能有中空期

所以就需要一种神奇的手法

看程序：

#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<algorithm>using namespace std;int dp[400000],mof[400000],walk[400000],m,s,t;//dp是技能，mof装的是魔法值，walk是跑步，dp，walk装的是跑的距离； int main(){    cin>>m>>s>>t;
   mof[0]=m;//定义边界
   for(int i=1;i<=t;i++){        if(mof[i-1]<10){
           mof[i]=mof[i-1]+4;
           dp[i]=dp[i-1];

}//如果没蓝了就会滥（dp数组只考虑技能） else {

       dp[i]=dp[i-1]+60;

       mof[i]=mof[i-1]-10;

}//有蓝了就闪现

walk[i]=max(dp[i-1]+17,walk[i-1]+17);//不管技能快还是跑步快，就以最优解为基础跑就行（主要是处理技能的中空期）

   if(walk[i]>=s||dp[i]>=s){//成功逃出荒岛

cout<<"Yes"<<endl<<i;

           return 0;
       }
   }    cout<<"No"<<endl<<max(walk[t],dp[t]);//死了
   return 0;
}