RQNOJ418[浪浪的小爱好]

动态规划，动规方程：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]));

}