bzoj 1010 斜率优化DP

我的第二道斜率DP。

收获：

　　1、假设两个位置:p<q<i，然后让某一位置优，看其满足什么性质，所谓斜率优化就是满足：

　　　　(g[q]-g[p])/(f[q]-f[p]) op h[i]

　　　　要化简成这样，必须满足f函数关于位置单调，否则op（<或>）的方向就会因为f的大小关系而变化，就没有凸的性质了。

　　2、斜率优化很难调试，所以当发现暴力DP和同样的方程被斜率优化了一下的答案不同时，不要去调试，直接去检查上面的各个函数是否写错或抄到代码中抄错了，

　　　　或者重推一遍。（注意决策点是否可能会重合）

 /**************************************************************

     Problem: 1010

     User: idy002

     Language: C++

     Result: Accepted

     Time:116 ms

     Memory:3148 kb

 ****************************************************************/

 #include <cstdio>

 #define ln(A,B) ((B)-(A))

 #define maxn 50010

 typedef long long lng;

 struct Vector {

     lng x, y;

     int id;

     Vector(){}

     Vector( lng x, lng y, int id ) : x(x), y(y), id(id) {}

     Vector operator-( const Vector & b ) const {

         return Vector( x-b.x, y-b.y, - );

     }

     lng operator&( const Vector & b ) const {

         return x*b.y-y*b.x;

     }

 };

 typedef Vector Point;

 int n, L;

 int cost[maxn];

 lng g[maxn], sum[maxn];

 lng dp[maxn];

 int beg, end;

 Point qu[maxn];

 inline lng sqr( lng a ) {

     return a*a;

 }

 int main() {

     scanf( "%d%d", &n, &L );

     sum[] = ;

     for( int i=; i<=n; i++ ) {

         scanf( "%d", cost+i );

         sum[i] = sum[i-]+cost[i];

         g[i] = sum[i]+i;

     }

     dp[] = ;

     qu[beg=end=] = Point( , ,  );

     for( int i=; i<=n; i++ ) {

         while( beg<end && (qu[beg+].y-qu[beg].y)<=(qu[beg+].x-qu[beg].x)**g[i] )

             beg++;

         int j = qu[beg].id;

         dp[i] = dp[j]+sqr(sum[i]-sum[j]-L+i-j-);

         Point npt = Point( g[i], dp[i]+g[i]*g[i]+*g[i]*(L+), i );

         while( beg<end && (ln(qu[end-],qu[end])&ln(qu[end-],npt))<= )

             end--;

         qu[++end] = npt;

     }

     printf( "%lld\n", dp[n] );

 }

巴特西

bzoj 1010 斜率优化DP

最新文章

热门文章