[HNOI2008]玩具装箱toy（dp+斜率优化）-白红宇

[HNOI2008]玩具装箱toy（dp+斜率优化）

阅读量：4309 次

发布时间：2019-06-06

本文共 1214 字，大约阅读时间需要 4 分钟。

斜率优化问题一般都是决策单调问题。对于这题能够证明单调决策。

令sum[i]=sigma(c [k] ) 1<=k<=i , f[i]=sum[i]+i , c=L+1;

首先我们能够写出转移方程 dp[i] = min( dp[j] + (f[i]-f[j]-c)^2 ) 。令决策j1<j2。若决策j2更优有

dp[j2]+(f[i]-f[j2]-c)^2<=dp[j1]+(f[i]-f[j1]-c)^2

能够得带 ((dp[j2]+f[j2]^2)-(dp[j1]+f[j1]^2) )/(f[j2]-f[j1])<2*(f[i]-c)。

优于f[i]是递增的，所以对于t>i的点。决策j2总是比j1更优。那么j1实际上能够从决策集合中删除。后面的就能够用一个队列维护了。

#include 
      
       #include 
       #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   using namespace std;typedef long long LL;const int inf = 0x3fffffff;const int mmax =50010;LL C[mmax];LL L,c;LL sum[mmax],f[mmax],dp[mmax];LL sqr(LL x){ return x*x;}double G(int x){ return 1.0*f[x]*f[x]+dp[x];}double S(int x){ return 2.0*f[x];}void calc(int i,int j){ dp[i]=dp[j]+sqr(f[i]-f[j]-c);}int Q[mmax];int main(){ int n; while(cin>>n>>L) { c=L+1; sum[0]=0; f[0]=0; for(int i=1;i<=n;i++) { scanf("%lld",&C[i]); sum[i]=sum[i-1]+C[i]; f[i]=sum[i]+i; } int head=0,tail=-1; dp[0]=0; Q[++tail]=0; for(int i=1;i<=n;i++) { while(head
                   
                    =tmp2) tail--; else break; } Q[++tail]=i; } printf("%lld\n",dp[n]); } return 0;}