官方题解

T6 午枫的陪伴时间

题目大意

有 $n$ 个开始陪伴的时间，每次陪伴必续连续陪 $t$ 天，期间不能进行别的陪伴的任务，如果陪伴需要花费 $cost$ 元，否则需要花费 $val$ 元，求最少花费。

解题思路

首先我们可以考虑按照 $a_i$ 从小到大排序，然后考虑通过DP如何解决。

设 $dp_{i,0}$ 表示前 $i$ 个选项，其中没选第 $i$ 项的最小花费； $dp_{i,1}$ 表示前 $i$ 个选项，其中选择了第 $i$ 项的最小花费。

其中 $dp_{i,0}$ 的状态转移很简单： $dp_{i,0}=min(dp_{i-1,0},dp_{i-1,1})+v_i$ 。

令 $s_i$ 为 $v_i$ 的前缀和，$pos$ 为 $i$ 左侧第一个小于 $a_i-m$ 的下标。那么 $dp_{i,1}$ 的状态转移为：$dp_{i,1}=min(dp_{pos,0},dp_{pos,1})+s_{i-1}-s_{pos}+cost_i$

最后答案取 $dp_{i,0}$ 和 $dp_{i,1}$ 的最小值即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define all(x) x.begin(),x.end()

signed main(){
    int n,m;cin>>n>>m;
    vector<array<int,3>>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i][0];
    for(int i=1;i<=n;i++) cin>>a[i][1]>>a[i][2];
    
    sort(a.begin()+1,a.end());
    vector<int>id(n+1);
    for(int i=1;i<=n;i++) id[i]=a[i][0];

    vector<int>s(n+1);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i][2];

    vector<vector<int>>dp(n+1,vector<int>(2)); // 0 - 不选 , 1 - 选
    for(int i=1;i<=n;i++){
        dp[i][0]=min(dp[i-1][0]+a[i][2],dp[i-1][1]+a[i][2]);

        int pos=upper_bound(all(id),max(0ll,a[i][0]-m))-id.begin()-1;
        dp[i][1]=min(dp[pos][0]+s[i-1]-s[pos]+a[i][1],dp[pos][1]+s[i-1]-s[pos]+a[i][1]);
    }
    
    cout<<min(dp[n][0],dp[n][1])<<endl;
}