【Kuangbin简单DP】挤奶时间-蒲公英云

【Kuangbin简单DP】挤奶时间

4561. 挤奶时间 - AcWing题库

题意：

思路：

一开始的思路是把这么多的区间当作物品，然后选与不选，这样去搞线性DP

显然是不行的，因为这样答案就不知道怎么统计了

而且，我们是设阶段！！按字面去理解，怎么可能把区间当作阶段啊

怎么按字面理解，其实就是去心里模拟一下过程，看看子问题就好了

应该是以时间当作阶段去定义状态

设dp[i]表示时刻 i 以内的最大挤奶量

然后去考虑转移

首先最大挤奶量一定大于等于前一个时刻的，因此dp[i]=dp[i-1]

题目的限制是，选择一个区间后，这个区间的右端点之后的 R 时间之后才能再选区间

所以这个时刻应该从这个时刻所在区间的左端点之前R的区间转移过来

所以我们需要预处理一个时刻作为右端点的区间的左端点和贡献c

Code：

#include <bits/stdc++.h>
using namespace std;
const int mxn=1e6+10;
vector<pair<int,int> > v[mxn];
int n,m,r,a,b,c;
int dp[mxn];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>r;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        v[b].push_back({a,c});
    }
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1];
        for(auto it:v[i]){
            dp[i]=max(dp[i],dp[max(it.first-r,0)]+it.second);
        }
    }
    cout<<dp[n]<<'\n';
}