链接:uva12594
题解
- 显然可以斜率优化,详情看代码
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
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;
}