2007 守望者的逃离（线性dp）

链接：https://ac.nowcoder.com/acm/contest/235/C
f[i] 表示在第i秒能跑到多远，先算出只放技能每秒能跑多远，再用跑步的方式“插缝”，即f[i] = max(f[i],f[i-1]-17) ;

#include <cstdio>
#include <algorithm>
using namespace std ;
const int N = 300005 ;
int f[N] ;
int main(){
    int m , s , t ;
    scanf ("%d%d%d",&m,&s,&t) ;
    for (int i = 1 ; i <= t ; i ++){
        if(m >= 10){
            f[i] = f[i-1] + 60 ;
            m -= 10 ;
        }
        else{
            f[i] = f[i-1] ;
            m += 4 ;
        }
    }
    for (int i = 1 ; i <= t ; i ++){
        f[i] = max(f[i],f[i-1]+17) ;
    }
    bool flag = false ;
    for (int i = 1 ; i <= t ; i ++){
        if (f[i] >= s){
            flag = true ;
            printf ("Yes\n%d\n",i) ;
            break ;
        }
    }
    if (!flag)    {
        printf ("No\n%d\n",f[t]) ;
    }
    return 0 ;
}