斜率优化

2/10/2017来源:ASP.NET技巧人气:808

http://www.lydsy.com/JudgeOnline/PRoblem.php?id=1010 Description P教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中。P教授有编号为1…N的N件玩具,第i件玩具经过压缩后变成一维长度为Ci.为了方便整理,P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具,那么两件玩具之间要加入一个单位长度的填充物,形式地说如果将第i件玩具到第j个玩具放到一个容器中,那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目,他可以制作出任意长度的容器,甚至超过L。但他希望费用最小. Input 第一行输入两个整数N,L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7 Output 输出最小费用 Sample Input 5 4 3 4 2 1 4 Sample Output 1

先列出n^2的dp: dp[i]=min(dp[j]+(sum[i]-sum[j]+i-j-1-L)^2) (j < i) 然后设循环中的k是最右解,j是普通解,列出不等式,化简成一侧是f【i】的,左侧是/的形式: (dp[k]+(f[k]+c)^2-dp[j]-(f[j]+c)^2)/2*(f[k]-f[j])<=f[i] 每个点是( (dp[k]+(f[k]+c)^2), 2*f[k] )

本来是把正常小于i的所有j循环,找最大的k…然后现在为了快点找k 所以推出这个关系, 对于所有j和那个点连起来斜率都小于等于f[i]的就是k,于是用f[i]去找最右下的点。 显然如果出现上凸的,用f[i]平移的话,最后一定不会是这个点,就没用了。所以就是个下凸的凸包。。。维护上面的点即可,还是个单调队列,不用二分找这个点,因为对于当前i满足这个式子的k和j对于i+1。。。f[i+1]>f[i]。所以一定还满足这个式子。。。就是个单调队列了=。=从头找,不合法的对后面的答案没有用了,就删掉(head++),找到第一个就一定是这个点,因为考虑图形是斜率逐渐增大的,第一个找到的点就是最右下的!

#include <cstdio> #include <iostream> #include <cstring> typedef long long LL; using namespace std; int n; const int nn=51000; LL l,c[nn],L; LL dp[nn]; LL sum[nn]; struct pll{ long long first,second; int pos; } stak[nn],tmp; int head,last; int cross(pll a,pll b,pll c){ return (b.first-a.first)*(c.second-a.second)-(c.first-a.first)*(b.second-a.second) > 0; } LL read() { LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void add(LL x,LL y,int i){ // cout <<"x = "<<x <<" y = "<<y<<endl; while(last > head){ tmp.first = x,tmp.second = y,tmp.pos = i; if(cross(stak[last-1],stak[last],tmp)) break; last--; } stak[++last].first = x; stak[last].second = y; stak[last].pos = i; // cout << stak[last].first <<" "<<stak[last].second<<endl; } void init(){ // scanf("%d",&n); // cin>>l; // l++; // for(int i = 1 ;i <= n;i++){ // cin>>c[i];//scanf("%I64d",&c[i]); // sum[i]=sum[i-1]+c[i]; // } // for(int i = 1; i <= n ; i++) // sum[i] += i; n=read();L=read();l=L+1; for(int i=1;i<=n;i++)c[i]=read(); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+c[i]; for(int i=1;i<=n;i++)sum[i]+=i; } double sp(pll k,pll j){ // cout <<" "<<(j.first-k.first)<<endl; return (j.second-k.second)/(j.first-k.first); } double check(int j,int k) { return (dp[k]+(sum[k]+l)*(sum[k]+l)-dp[j]-(sum[j]+l)*(sum[j]+l))/(2.0*(sum[k]-sum[j])); } void sov(){ dp[0]=0; head = 1; last = 1; stak[1].first = stak[1].second = stak[1].pos = 0; for(int i=1;i<=n;i++){ // cout <<i <<endl; while(head < last && check(stak[head].pos,stak[head+1].pos)<=sum[i]) head++; int t = stak[head].pos; // cout<<"t = "<<t<<endl; // printf("sum[%d] = %I64d sum[%d] = %I64d \n",i,sum[i],t,sum[t]); dp[i] = dp[t]+(sum[i]-sum[t]-l)*(sum[i]-sum[t]-l); // cout<<"dp = "<<dp[i]<<endl; // add(2*sum[i],dp[i]+(sum[i]+l)*(sum[i]+l),i); tmp.first = 2*sum[i];tmp.second = dp[i]+(sum[i]+l)*(sum[i]+l);tmp.pos = i; while(head < last && check(stak[last].pos,tmp.pos)< check(stak[last-1].pos,stak[last].pos))last--; stak[++last]=tmp; // cout <<"y = "<<dp[i]+(sum[i]+l)*(sum[i]+l) << " x = "<<2*sum[i]<<endl; } // for(int i = 1; i <= n ; i++) // printf("dp[%d] = %I64d\n",i,dp[i]); cout<<dp[n]<<endl;//printf("%I64d\n",dp[n]); } int main(){ init(); sov(); return 0; }

特别行动队。 http://www.lydsy.com/JudgeOnline/problem.php?id=1911 上凸包,其实可以直接判断等式,而不用叉乘判断凸包,都一样。

#include <cstdio> #include <iostream> #include <cstring> using namespace std; int n,A,B,C,head,last; const int maxn = 1e6+10; long long a[maxn],sum[maxn],f[maxn],q[maxn]; void init(){ scanf("%d",&n); scanf("%d%d%d",&A,&B,&C); for(int i = 1; i <= n ; i++){ scanf("%lld",&a[i]); sum[i] = sum[i-1]+a[i]; } } double check(int j,int k){ return (double)(f[k]-f[j]+A*((sum[k]*sum[k])-(sum[j]*sum[j]))+B*(sum[j]-sum[k]))/(2.0*(sum[k]-sum[j])*A); } void sov(){ head = last = 1;q[1] = 0; for(int i = 1; i <= n ; i++){ while(head < last && check(q[head],q[head+1]) <= sum[i]) head++; f[i] = f[q[head]]+A*(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]])+B*(sum[i]-sum[q[head]])+C; while(head < last&& check(q[last-1],q[last]) > check(q[last],i)) last--; q[++last] = i; } printf("%lld\n",f[n]); } int main(){ init(); sov(); }