【Kuangbin简单DP】挤奶时间

淡淡的烟草味﹌ 2024-03-30 13:55 57阅读 0赞

[4561. 挤奶时间 - AcWing题库][4561. _ - AcWing]

题意：

![a7a55a20fbce46518570f69b7dea4542.png][]

思路：

一开始的思路是把这么多的区间当作物品，然后选与不选，这样去搞线性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';
    }

**总结：**

**状态设计又加了个trick：按字面意思去设计阶段，不要嗯线性设计**

[4561. _ - AcWing]: https://www.acwing.com/problem/content/4564/
[a7a55a20fbce46518570f69b7dea4542.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/74331e3c692744f094459e5300428bc9.png