线性DP P1267

则 f[i]=f[i+1]+1 (i=p[j]) 

f[i]=max{f[i],f[p[j]+t[j]]} (i<>p[j]) 

最后输出f[1]即可。设f[i]表示从 i 到 n 时间内的最大空闲时间。 

则 f[i]=f[i+1]+1 (i=p[j]) 

f[i]=max{f[i],f[p[j]+t[j]]} (i<>p[j]) 

最后输出f[1]即可。

#include<cstdio>

#...

P1267

设f[i]表示从 i 到 n 时间内的最大空闲时间。 

则 f[i]=f[i+1]+1 (i=p[j]) 

f[i]=max{f[i],f[p[j]+t[j]]} (i<>p[j]) 

最后输出f[1]即可。设f[i]表示从 i 到 n 时间内的最大空闲时间。 

则 f[i]=f[i+1]+1 (i=p[j]) 

f[i]=max{f[i],f[p[j]+t[j]]} (i<>p[j]) 

最后输出f[1]即可。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#define F(i,s,e) for(int i=s;i<=e;i++)

#define D(i,e,s) for(int i=e;i>=s;i--)

using namespace std;

int p[10100],t[10100];

int f[10100];

int n,k;

int main()

{

    memset(f,0,sizeof(f));

    scanf("%d%d",&n,&k);

    F(i,1,k)

        scanf("%d%d",&p[i],&t[i]);

    int j=k;

    D(i,n,0)

    {

        if(i!=p[j])

            f[i]=f[i+1]+1;

        else

        {

            while(i==p[j])

            {

f[i]=max(f[i],f[p[j]+t[j]]);

j--;

}

        }

    }

    printf("%d\n",f[1]);

    return 0;

}