http://www.lydsy.com/JudgeOnline/problem.php?id=1571
DP不一定全部全状态转移
贪心的舍去一些不合法的反而更容易转移
在一定能力范围内，肯定滑雪所需时间越少越好
当课程的结束时间和能力值改变相同时，肯定课程越晚开始越好
预处理
late[i][j] 表示结束时间为i，能力值变成j的课程的最晚开始时间
mi[i] 表示在滑雪能力值<=i时，滑一次雪所需的最短时间
dp[i][j] 表示时间i，能力值为j时，最多的滑雪次数
f[i] 表示时间i最多的滑雪次数
喝可可：dp[i][j]=dp[i-1][j]
上课：dp[i][j]=f[late[i][j]]
滑雪：dp[i][j]=dp[i-mi[j]][j]+1
f[i]=max(dp[i][j])
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; #define N 101
#define M 10001 int dp[M][N],f[M]; int late[M][N],mi[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int main()
{
int t,s,n;
read(t);
read(s);
read(n);
int start,last,turn;
for(int i=;i<=s;++i)
{
read(start);
read(last);
read(turn);
late[start+last][turn]=max(late[start+last][turn],start);
}
int need,tim;
memset(mi,,sizeof(mi));
for(int i=;i<=n;++i)
{
read(need);
read(tim);
mi[need]=min(mi[need],tim);
}
for(int i=;i<=;++i) mi[i]=min(mi[i],mi[i-]);
memset(dp,,sizeof(dp));
dp[][]=f[]=;
for(int i=;i<=t;++i)
for(int j=;j<=;++j)
{
dp[i][j]=dp[i-][j];
if(late[i][j]) dp[i][j]=max(dp[i][j],f[late[i][j]]);
if(i-mi[j]>=) dp[i][j]=max(dp[i][j],dp[i-mi[j]][j]+);
f[i]=max(f[i],dp[i][j]);
}
cout<<f[t];
}