https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=337
-
这道题算DP纯粹是个幌子，其实就是一个贪心的过程。
-
为什么要留后面价格贵的油？因为可能不够用，先存着；而如果前面的贵，由于有 \(T\) 限制，所以在能够装满的同种情况下，用后面的油价格更低。我们这个计算是用多少算多少，就跟洛谷计算空间一样，存下来的油用不完反正没有计入总费用中。
具体而言，枚举到一个 \(i\)，先看一下满油能否到达下一个位置，然后先在出发前替换劣油，最后计算到达 \(i+1\) 的消耗。
#include<iostream>
using namespace std;
typedef long long ll;
const int N=100010;
int n,t,d[N],p[N],cur,q[N];
ll ans;
int main(){
#ifdef LOCAL
freopen("1.txt","r",stdin);
#endif
#ifndef LOCAL
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
#endif
cin>>n>>t;
int hh=0,tt=-1;
for(int i=0;i<n;++i){
cin>>d[i]>>p[i];
int dis=d[i];
if(t<d[i]){
cout<<"-1";
return 0;
}
while(hh<=tt&&p[q[tt]]>=p[i]){
cur-=d[q[tt]];
--tt;
}
d[i]=t-cur;
q[++tt]=i;
cur=t-dis;
while(hh<=tt){
int f=q[hh++];
if(d[f]>=dis){
d[f]-=dis;
ans+=1ll*dis*p[f];
if(d[f])--hh;
break;
}
else dis-=d[f],ans+=1ll*d[f]*p[f];
}
}
cout<<ans;
return 0;
}