洛谷动态规划题单clickhere~

线性dp

1. 洛谷P1095

其实我也没看懂为什么是线性dp，我反正写了个二维的

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,s,t;
    cin>>m>>s>>t;
    int c=m/10;m=m%10;
    int cc=min(c,t);
    if(cc*60>=s)
    {
        cout<<"Yes"<<endl;
        for(int i=0;i<=cc;i++)
        if(i*60>=s)
        {
            cout<<i<<endl;
            break;
        }
    }
    else if(t<=c)
    cout<<"No"<<endl<<cc*60<<endl; 
    else
    {
        s-=c*60;
        t-=c;
        int dpt[t+1][15];
        memset(dpt,0,sizeof(dpt));
        for(int i=1;i<t+1;i++)
        for(int j=0;j<15;j++)//dpt[i][j]指当时间还剩i秒，魔力还剩j点的时候，能跑的最远距离
        {
            if(j<10)dpt[i][j]=max(dpt[i-1][j]+17,dpt[i-1][j+4]);
            else dpt[i][j]=60+dpt[i-1][j-10];
        }
        if(dpt[t][m]<s)
        cout<<"No"<<endl<<dpt[t][m]+c*60<<endl;
        else
        {
            cout<<"Yes"<<endl;
            int i;
            for(i=t-1;i>0;i--)
            if(dpt[i][m]<s)
            break;
            cout<<i+1+c<<endl;
        }
    }
    return 0;
}