最速题解

#include<bits/stdc++.h>
using namespace std;
//午枫是gay吗
//这不绿题我退钱
struct x{
    long long a,c,v;
}d[1000005];
bool cmp(x jojo,x dio){
    return jojo.a<dio.a;
}
bool cmp1(pair<long long,long long> a, pair<long long,long long> b) {
	return a.second>b.second;
}
long long n,t,dp[1000005][2],s[1000005],cnt;
priority_queue<pair<long long,long long>,vector<pair<long long,long long> >,bool(*)(pair<long long,long long>, pair<long long,long long>)> q(cmp1);
int main(){
  	ios::sync_with_stdio(0);
  	cin.tie(NULL);cout.tie(NULL);
    cin>>n>>t;
    for(int i=1;i<=n;++i)cin>>d[i].a;
    for(int i=1;i<=n;++i)cin>>d[i].c>>d[i].v;
    sort(d+1,d+n+1,cmp);
    for(int i=1;i<=n;++i){
        s[i]=s[i-1]+d[i].v;
    }
    int ii=1;
    for(;d[ii].a<=t&&ii<=n;++ii){
    	dp[ii][1]=s[ii-1]+d[ii].c;
        dp[ii][0]=min(dp[ii-1][0],dp[ii-1][1])+d[ii].v;
    }
    cnt=1;
    for(int i=ii;i<=n;++i){
        while(cnt<=n&&d[cnt].a<=d[i].a-t){q.push(make_pair(cnt,dp[cnt][1]+(s[n]-s[cnt])));++cnt;}
        if(!q.empty())dp[i][1]=min(q.top().second-(s[n]-s[q.top().first])+(s[i-1]-s[q.top().first]),s[i-1])+d[i].c;
        else dp[i][1]=s[i-1]+d[i].c;
        dp[i][0]=min(dp[i-1][0],dp[i-1][1])+d[i].v;
    }
    cout<<min(dp[n][0],dp[n][1]);
    return 0;
}

以上是当时的代码。下面是分析。
努力观察得出状态转移方程：如果当前天数小于t，你只能选一天陪伴，因此第i天不选就要全盘收下dpi-1+vi，而某一天选了就不能选其他，要花费前面的v和ci
如果大于t，选第i个要找i-t以前的状态加上这个状态到i的v的总值的最优解，而不选第1个直接沿用以前的dp再加上vi
恭喜你喜提TLE。
累加vi可以看出要用前缀和，而找最小可以用优先队列优化。
O（nlogn）的复杂度