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]));


}