luogu P1095守望者的逃离【dp】By cellur925

考虑dp，设f[i]表示到第i时间，能到达的最远距离。因为题目涉及了三种操作：1，补血消耗魔法值；2，等待增加魔法值；3，直接向前走。而1,3和2,3的操作是可以同时进行没有冲突的，所以我们可以分开处理。

先预处理出使用魔法的情况，再跑一遍朴素走的情况即可。

Code

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int m,s,t;

 int f[];

 int main()

 {

     scanf("%d%d%d",&m,&s,&t);

     for(int i=;i<=t;i++)

     {

         if(m>=) m-=,f[i]=f[i-]+;

         else m+=,f[i]=f[i-];

     }

     for(int i=;i<=t;i++)

     {

         f[i]=max(f[i-]+,f[i]);

         if(f[i]>=s)

         {

             printf("Yes\n");

             printf("%d",i);

             return ;

         }

     }

     printf("No\n");

     printf("%d",f[t]);

     return ;

 }

我dp太弱了这么水的题还要看题解

巴特西

luogu P1095守望者的逃离【dp】By cellur925

最新文章

热门文章