uva12594

链接:uva12594

题解

于是 k+1~i划为一组

  • 显然可以斜率优化,详情看代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int N=20007;
    char str[50],ptr[N];
    ll a[N],nm[N],sum[N],res[N],dp[507][N];
    int n,m,T,len=26,q[N];
    inline void init(){
    scanf("%s%d",str+1,&m);
    rep(i,1,len)nm[str[i]-'a']=i-1;
    scanf("%s",ptr+1);
    n=strlen(ptr+1);
    rep(i,1,n)a[i]=nm[ptr[i]-'a'];
    rep(i,1,n){
    sum[i]=sum[i-1]+(i-1-a[i])*a[i];
    res[i]=res[i-1]+a[i];
    }
    rep(i,1,n)dp[1][i]=sum[i];
    }
    inline ll Y(int x,int y,int c){return dp[c][x]-sum[x]+res[x]*x-(dp[c][y]-sum[y]+res[y]*y);}
    inline ll X(int x,int y){return x-y;}
    int main(){
    scanf("%d",&T);
    rep(cnt,1,T){
    init();
    rep(j,2,m){
    int head=1,tail=0;
    //q[++tail]=1;
    rep(i,1,n){
    while(head<tail&&Y(q[head+1],q[head],j-1)<=X(q[head+1],q[head])*res[i])++head;
    dp[j][i]=dp[j-1][q[head]]+sum[i]-sum[q[head]]-(res[i]-res[q[head]])*q[head];
    while(head<tail&&Y(q[tail],i-1,j-1)*X(q[tail-1],q[tail])<Y(q[tail-1],q[tail],j-1)*X(q[tail],i-1))--tail;
    q[++tail]=i-1;
    }
    }
    printf("Case %d: %lld\n",cnt,dp[m][n]);
    }
    return 0;
    }