题解 P2948

· · 题解

此题为比较基础的一道DP

楼上题解的做法都是二维DP或记搜，我这里推荐一种一维DP的方法。

我们观察到能力值是绝对的，而不是增长值，且能力值非常小。所以我们考虑把课程按照开始时间进行排序，再用sum[i]记录能力值达到i时的滑雪速度。

然后我们用动态规划，用dp[i]记录第i节课时候我们最多可以完成多少作业，为了方便起见，我们让x[0].start=1，并且让x[m+1].start=T+1，这样就方便进行时间的删减操作了。

以上我们可以得出这题的状态转移方程：

dp[i]=max(dp[i],dp[j]+(x[i].s-x[j].s-x[j].t)/sum[x[j].c])

最终代码如下：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const ll N=110000;
const ll M=110;
ll t,m,n,ans;
ll dp[N],sum[N];
struct Nodem{ll t,s,c;}x[M];
bool cp(Nodem PRO,Nodem PRE){return PRO.t==PRE.t?PRO.s<PRE.s:PRO.t<PRE.t;}
int main()
{
    memset(sum,inf,sizeof(sum));
    scanf("%lld%lld%lld",&t,&m,&n);
    for(ll i=1;i<=m;i++) scanf("%lld%lld%lld",&x[i].t,&x[i].s,&x[i].c);
    for(ll i=1,u,v;i<=n;i++) scanf("%lld%lld",&v,&u),sum[v]=min(sum[v],u);
    sort(x+1,x+1+m,cp);
    x[0].t=1;x[0].s=0;x[0].c=1;x[m+1].t=t+1;
    for(ll i=1;i<=M;i++) sum[i]=min(sum[i-1],sum[i]);
    for(ll i=1;i<=m+1;i++) 
        for(ll j=0;j<i;j++) 
            dp[i]=max(dp[i],dp[j]+(x[i].t-x[j].s-x[j].t)/sum[x[j].c]);
    printf("%lld\n",dp[m+1]);
    return 0;
}