「bsoj5043」鏖战字符串 - 动态规划+斜率优化+单调队列/数据结构 | Bill Yang's Blog

「bsoj5043」鏖战字符串 - 动态规划+斜率优化+单调队列/数据结构

题目大意

“量子态的字符串”非常顽固,只能先分割成若干个子串,然后再通过以下两种方式删除:
1、假设子串的所有字符的删除难度之和为x,消耗a*x^2+b的时间可以将子串扔进回收站。
2、若子串中出现次数最多的字符出现的次数不少于L次且不多于r次,那么采用“量子态的py自动机”算法可以消耗c*x+d的时间将子串扔进回收站。
Abwad自然知道最少用多少时间就能将字符串删去,因此,他希望你求出删去每个前缀[1,i]的最少用时。


题目分析

任意分割显然可以转化为分割一次,对原问题没有影响,那么我们便可以转化为子问题,可以用动态规划解决。

设$f[i]$表示删去前缀$[1,i]$的最少用时。
不难得出状态转移方程:

对于第一个转移方程

显然是一个比较裸的斜率优化,展开后得到:

斜率优化讲解可以看这里
我们可以以$f[j]+asum[j]^2$为纵坐标,以$2asum[i]$为斜率,以$sum[j]$为横坐标进行斜率优化。
因为$k$与$x$均单调,所以不需要cdq分治,直接使用单调队列维护下凸壳。

对于第二个转移方程

经过分析,$j$能够取到的范围必定是一段连续区间。
由于式子中$i$与$j$分离,可以用单调队列维护(achen就是这么写的),然而求区间最值我还是喜欢使用线段树维护。

首先我们可以通过二分找到这段$j$的合法区间,然后通过线段树查询这段区间的最小值。

细节

虽然想法很显然,但是考试时的我并没有调出来,细节太多。
比如二分边界情况,斜率的$x$之差为0等等,所以需要调一阵,能1A还是很不错的。


代码

暴力50分

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
47
48
49
50
51
52
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
LL n,a,b,c,d,l,r,Hash[100005][28],sum[100005],f[100005];
char s[100005];
int main() {
n=Get_Int();
a=Get_Int();
b=Get_Int();
c=Get_Int();
d=Get_Int();
l=Get_Int();
r=Get_Int();
scanf("%s",s);
for(int i=1; i<=n; i++) {
for(int j=0; j<26; j++)Hash[i][j]=Hash[i-1][j];
Hash[i][s[i-1]-'a']++;
sum[i]=sum[i-1]+Get_Int();
f[i]=1e17;
}
f[0]=0;
for(int i=1; i<=n; i++)
for(int j=0; j<i; j++) {
f[i]=min(f[i],f[j]+a*(sum[i]-sum[j])*(sum[i]-sum[j])+b);
LL Max=0;
for(int k=0; k<26; k++)Max=max(Max,Hash[i][k]-Hash[j][k]);
if(Max>=l&&Max<=r)f[i]=min(f[i],f[j]+c*(sum[i]-sum[j])+d);
}
for(int i=1; i<=n; i++)printf("%lld\n",f[i]);
return 0;
}

100分

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
LL n,a,b,c,d,l,r,Hash[maxn][28],sum[maxn],f[maxn],Q[maxn];
char s[maxn];
struct Tree {
int left,right;
LL min;
Tree(int l=0,int r=0,LL m=1e17):left(l),right(r),min(m) {}
};
struct Segment_Tree {
Tree tree[maxn*4];
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right) {
tree[index]=Tree(Left,Right);
if(Left==Right) {
if(Left==0)tree[index].min=0;
return;
}
int mid=(Left+Right)>>1;
build(ls,Left,mid);
build(rs,mid+1,Right);
push_up(index);
}
void push_up(int index) {
tree[index].min=min(tree[ls].min,tree[rs].min);
}
void modify(int index,int target,LL v) {
if(target<tree[index].left||target>tree[index].right)return;
if(tree[index].left==tree[index].right) {
tree[index].min=v;
return;
}
modify(ls,target,v);
modify(rs,target,v);
push_up(index);
}
LL query(int index,int Left,int Right) {
if(Right<tree[index].left||Left>tree[index].right)return 1e17;
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].min;
return min(query(ls,Left,Right),query(rs,Left,Right));
}
} st;
double Slope(int x,int y) {
if(sum[x]==sum[y]) {
if(f[y]+sum[y]*sum[y]*a-f[x]-sum[x]*sum[x]*a>=0)return 1e18;
else return -1e18;
}
return (double)(f[y]+sum[y]*sum[y]*a-f[x]-sum[x]*sum[x]*a)/(sum[y]-sum[x]);
}
int Binary1(int Left,int Right) {
int right=Right+1;
while(Left<=Right) {
int mid=(Left+Right)>>1;
LL Max=0;
for(int k=0; k<26; k++)Max=max(Max,Hash[right][k]-Hash[mid][k]);
if(Max>=l)Left=mid+1;
else Right=mid-1;
}
return Left;
}
int Binary2(int Left,int Right) {
int right=Right+1;
while(Left<=Right) {
int mid=(Left+Right)>>1;
LL Max=0;
for(int k=0; k<26; k++)Max=max(Max,Hash[right][k]-Hash[mid][k]);
if(Max<=r)Right=mid-1;
else Left=mid+1;
}
return Left;
}
int main() {
n=Get_Int();
a=Get_Int();
b=Get_Int();
c=Get_Int();
d=Get_Int();
l=Get_Int();
r=Get_Int();
scanf("%s",s);
for(int i=1; i<=n; i++) {
for(int j=0; j<26; j++)Hash[i][j]=Hash[i-1][j];
Hash[i][s[i-1]-'a']++;
sum[i]=sum[i-1]+Get_Int();
f[i]=1e17;
}
int Left=1,Right=1;
Q[1]=0;
f[0]=0;
st.build(1,0,n);
for(int i=1; i<=n; i++) {
while(Left<Right&&Slope(Q[Left],Q[Left+1])<=2*a*sum[i])Left++;
int j=Q[Left];
f[i]=f[j]+a*(sum[i]-sum[j])*(sum[i]-sum[j])+b;
int right=Binary1(0,i-1)-1,left=Binary2(0,i-1);
if(left<=right)f[i]=min(f[i],st.query(1,left,right)+c*sum[i]+d);
st.modify(1,i,f[i]-c*sum[i]);
while(Left<Right&&Slope(Q[Right-1],Q[Right])>=Slope(Q[Right],i))Right--;
Q[++Right]=i;
}
for(int i=1; i<=n; i++)printf("%lld\n",f[i]);
return 0;
}

姥爷们赏瓶冰阔落吧~
0%