题目大意
“量子态的字符串”非常顽固，只能先分割成若干个子串，然后再通过以下两种方式删除：
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
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
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];
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;
}
