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

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

RQNOJ418[浪浪的小爱好]  

2010-07-24 11:39:16|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

动态规划,动规方程:f[i]=min{f[j]+cost(j,i)},cost(j,i)=m+sqr(s[i]-s[j]),s[i]表示从1到i这些音节的距离和。

然后朴素的一定TLE,所以斜率优化,见这里

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-24

DESCRIPTION:

动态规划 专练

http://www.rqnoj.cn/Problem_418.html

*/

#include <stdio.h>

 

const int oo=(~0u)>>1;

const int MAXN=200000;

int n,m;

char a[MAXN+2];

char b[MAXN+2];

long long int s[MAXN+2];

long long int f[MAXN+2];

int q[MAXN+2];

int head,tail;

int main()

{

    //f[i]=min{f[j]+cost(j,i)}

    //cost(j,i)=m+sqr(s[i]-s[j])

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

    scanf("%s%s",&a,&b);

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

        s[i+1]=s[i]+(a[i]>=b[i]?a[i]-b[i]:b[i]-a[i]);

    #define value(j) f[j]+(s[i]-s[j])*(s[i]-s[j])+m

    #define ky(k,j) (f[k]-f[j]+s[k]*s[k]-s[j]*s[j])

    #define kx(k,j) (s[k]-s[j])

    q[head=tail=0]=0;

    f[0]=-m;

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

    {

        while (head<tail&&value(q[head])>=value(q[head+1])) head++;

        int j=q[head];

        f[i]=value(j);

        while (head<tail&&(s[q[tail]]==s[i]||ky(q[tail-1],q[tail])*kx(q[tail],i)>=ky(q[tail],i)*kx(q[tail-1],q[tail]))) tail--;

        q[++tail]=i;

    }

    printf("%d\n",int(f[n]));

}

 

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

历史上的今天

评论

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

页脚

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