题目：http://ch.ezoj.tk/contest/CH%20Round%20%2359%20-%20OrzCC杯NOIP模拟赛day1/队爷的Au%20Plan
题解：看了题之后觉得肯定是DP+优化，因为昨天刚水了一道线段树优化DP的题，所以又想到线段树上去了。。。
具体做法：
我维护了一个单调递增的f，显然若i<j并且f[i]>f[j]，那么f[j]就可以不用
然后我们要找寻>=a[i]的就是连续的一段了，就可以用线段树来查询f[j]-s[j]的最大值了
然后 n*logn 水过，居然拿下了first blood
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 250000
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,m,tot,a[maxn],b[maxn],f[maxn];
struct seg{int l,r,mx;}t[*maxn];
void build(int k,int l,int r)
{
t[k].l=l;t[k].r=r;int mid=(l+r)>>;t[k].mx=-inf;
if(l==r)return;
build(k<<,l,mid);build(k<<|,mid+,r);
}
void change(int k,int x,int y)
{
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==r){t[k].mx=max(t[k].mx,y);return;}
if(x<=mid)change(k<<,x,y);else change(k<<|,x,y);
t[k].mx=max(t[k<<].mx,t[k<<|].mx);
}
int query(int k,int x,int y)
{
int l=t[k].l,r=t[k].r,mid=(l+r)>>;
if(l==x&&r==y)return t[k].mx;
if(y<=mid)return query(k<<,x,y);
else if(x>mid)return query(k<<|,x,y);
else return max(query(k<<,x,mid),query(k<<|,mid+,y));
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();m=read();
for1(i,n)a[i]=read();
for1(i,n)b[i]=b[i-]+read();
build(,,n);
f[tot=]=m;change(,,m);
//for1(i,4*n)cout<<i<<' '<<t[i].l<<' '<<t[i].r<<' '<<t[i].mx<<endl;
for1(i,n)
{
int x=lower_bound(f,f+tot+,a[i])-f,y;
if(f[x]<a[i])continue;else y=query(,x,tot);
//for0(j,tot)cout<<j<<' '<<f[j]<<endl;
//cout<<i<<' '<<x<<' '<<y<<endl;
if(i==n){printf("%d\n",y+b[i]-a[i]);return ;}
if(y+b[i]-a[i]>f[tot])
{
//cout<<tot<<' '<<f[tot]<<endl;
f[++tot]=y+b[i]-a[i];
change(,tot,f[tot]-b[i]);
}
}
return ;
}
赛后发现别人的代码都很短，瞬间惊呆
出题人说：
对于i状态，考虑j，k两个决策，j<k<i且f[j]>hard[i]&&f[k]>hard[i]。
若j，k不为前面同一个决策转移得到，则k的决策层数显然会更大，即额外消耗更多，所以j优于k；
若j，k为前面同一个决策l转移得到：
f[j]=f[l]-sum[l]+sum[j]-hard[j]
f[k]=f[l]-sum[l]+sum[k]-hard[k]
f[j]-f[k]=sum[j]-sum[k]+hard[k]-hard[j]
f[j]-sum[j]-(f[k]-sum[k])=hard[k]-hard[j]
即f[j]-sum[j]> f[k]-sum[k],
所以j决策优于k决策， 所以对于每一个状态i，最小的能够转移到i的决策总是最优的，这样只需要用单调队列维护决策即可（其实一个指针就OK了），时间复杂度为O(n)。
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 250000
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,m,tot,a[maxn],b[maxn],f[maxn];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();f[]=read();
for1(i,n)a[i]=read();
for1(i,n)b[i]=b[i-]+read();
int j=;
for1(i,n)
{
while(f[j]<a[i])j++;
f[i]=f[j]+b[i]-b[j]-a[i];
}
printf("%d\n",f[n]);
return ;
}
出题人没卡线段树真是太良心了。好评！