[10.2模拟] plan

题意:给出n个物品,你有一个兴奋值,拿走一个物品需要花费(hrad_i)的代价((hrad_i)递增),拿完之后你的兴奋值可以增加(s_i),你可以拿走所有(hard_i)小于兴奋值的物品,问拿完所有物品后的最大兴奋值

题解:

dp+单调队列优化

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define N 200010
using namespace std;

int n,m,h,t,dp[N],hard[N],q[N],sum[N];

int gi() {
  int x=0,o=1; char ch=getchar();
  while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
  if(ch=='-') o=-1,ch=getchar();
  while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
  return o*x;
}

int main() {
  n=gi(),m=gi();
  for(int i=1; i<=n; i++) hard[i]=gi();
  for(int i=1; i<=n; i++) sum[i]=sum[i-1]+gi();
  q[h=t=1]=0,dp[0]=m;
  for(int i=1; i<=n; i++) {
    while(h<t && dp[q[h]]<hard[i]) h++;
    dp[i]=dp[q[h]]-sum[q[h]]+sum[i]-hard[i];
    while(h<t && dp[q[h]]-sum[q[h]]<=dp[i]-sum[i]) t--;
    q[++t]=i;
  }
  printf("%d", dp[n]);
  return 0;
}