[BZOJ1010]玩具装箱：DP决策单调性

本文主要是介绍[BZOJ1010]玩具装箱：DP决策单调性，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目请点击这里

首先可以得到方程：

f[i]=max{f[j]+(sum[i]-sum[j]+i-j-1-L)^2}

显而易见该方程具有单调性，因此可以使用决策单调性优化，维护一个下凸壳，每次将当前队首决策取出直至当前决策为最优，然后将当前点加入队尾，若有斜率小于当前点的则先取出后加入。

/*
User:Small
Language:C++
Problem No.:1010
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int M=50005;
int n,l,a[M],c,q[M];
ll sum[M],f[M];
double slop(int j,int k){return (f[k]-f[j]+(sum[k]+c)*(sum[k]+c)-(sum[j]+c)*(sum[j]+c))/(2.0*(sum[k]-sum[j]));
}
void solve(){int l,r;l=1;r=0;q[++r]=0;for(int i=1;i<=n;i++){while(l<r&&slop(q[l],q[l+1])<=sum[i]) l++;int t=q[l];f[i]=f[t]+(sum[i]-sum[t]-c)*(sum[i]-sum[t]-c);while(l<r&&slop(q[r],i)<slop(q[r-1],q[r])) r--;q[++r]=i;}
}
int main(){freopen("data.in","r",stdin);//ios::sync_with_stdio(false);cin>>n>>l;c=l+1;for(int i=1;i<=n;i++){cin>>a[i];sum[i]=sum[i-1]+a[i]+1;}solve();cout<<f[n]<<endl;return 0;
}

这篇关于[BZOJ1010]玩具装箱：DP决策单调性的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---