注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

 
 
 

日志

 
 

【转载】斜率优化DP  

2014-03-24 11:33:41|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本文转载自YoMean!《斜率优化DP》
最近比较懒 没怎么写东西了 就贴一个别人的吧
-------------------------------------------------------------------------------------------
入门论文有《浅谈数形结合思想在信息学竞赛中的应用》,大家可以从里面的例二得到斜率优化的启示。同时,这个例二也是一道基础的斜率优化题目。
进阶的有《用单调性优化动态规划》,里面由浅入深地介绍了斜率优化。
四边形优化的论文《四边形不等式优化DP》。
很多的四边形不等式优化的DP都可以转换成斜率优化。
而在斜率优化里面,状态转移方程一般为:dp[i] = min (dp[j] + w[i,j]);  w[i,j] 一般可以转化成与i和j有关的变量。那转移方程可以变成 
dp[i] = min (dp[j] + k*c[j] + const)  = min (dp[j] + k * c[j])  + const 其中,k和const与i有关。这时,我们将dp[j]作为y,c[j] 作为x,作为平面上的点。然后再用一条斜率为k的边在平面上平移,找到在平面上找一个让dp[i]的值最小的决策。很明显,这样的决策一定是在凸包上的。所以,同时要维护凸包。不过,这样的优化适用对斜率与某一坐标单调的情况。不单调的话,要用到平衡树动态维护凸包。
hdu 4258:

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 1000050

#define __int64 long long

using namespace std;

//dp[i] = dp[j] + val[j + 1] ^ 2 + val[i] ^ 2 - 2 * val[i] * val[j + 1] + c

//y = dp[j] + val[j + 1] ^ 2   x = val[j + 1]  k = -2 * val[i] const = c + val[i] ^ 2

__int64 x[N],y[N],dp[N],val[N],c;

int q[N],top,pp;

int n;


__int64 cross (int a,int b,int c) {

    __int64 x1 = x[b] - x[a],y1 = y[b] - y[a];

    __int64 x2 = x[c] - x[a],y2 = y[c] - y[a];

    return x1 * y2 - x2 * y1;

}


__int64 check (int a,__int64 k){

    return y[a] - k * x[a];

}


void in (__int64 &a){

    char c;

    while ( (c = getchar()) < '0' || c > '9');

    a = c - '0';

    while ( (c = getchar()) >= '0' && c <= '9') a = a * 10 + c - '0';

}


int main (){

    while (~scanf ("%d%lld",&n,&c)){

        if (n + c == 0) break;

        for (int i = 1;i <= n;i ++) in (val[i]);//scanf ("%lld",&val[i]);

        dp[0] = 0;

        q[0] = pp = top = 0;

        if (n == 1){printf ("%lld\n",c);continue;}

        x[0] = val[1];

        y[0] = val[1] * val[1];

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

            while (pp < top && check(q[pp], 2 * val[i]) > check(q[pp + 1], 2 * val[i])) pp ++;

            dp[i] = check(q[pp], 2 * val[i]) + c + val[i] * val[i];

            x[i] = val[i + 1],y[i] = dp[i] + val[i + 1] * val[i + 1];

            while (top > pp && cross(q[top - 1], q[top], i) <= 0) top --;

            q[++ top] = i;

        }

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

    }

    return 0;

}

  评论这张
 
阅读(31)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017