codeforces Good bye 2016 E 线段树维护dp区间合并

时间:2021-05-08 02:41:23

codeforces Good bye 2016 E 线段树维护dp区间合并

题目大意:给你一个字符串,范围为‘0’~'9',定义一个ugly的串,即串中的子串不能有2016,但是一定要有2017,问,最少删除多少个字符,使得串中符合ugly串?

思路:定义dp(i, j),其中i=5,j=5,因为只需要删除2016当中其中一个即可,所以一共所需要删除的字符和需要的字符为20176,因此i和j只要5就够了。

然后转移就是dp(i,i) = 0, 如果说区间大小为1的话,那么如果是2017中的一个,那么就是dp(pos, pos+1) = 0, dp(pos,pos) = 1。但是如果pos为'6'这个字符,那么定义6这个pos=x转移就要为dp[x-1][x-1] = dp[x][x] = 1.然后我们再去转移就好了。

然后最后一定要注意线段树的合并顺序哦

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
/*
定义dp(x,i,j)表示区间[0,x)内能够获得的2017的前缀长度为i的,至少要删除多少个字符
最少要删除多少个才能构成前缀为j的2017,然后我们不需要去管x,只需要用线段树去维护i,j即可。
*/
const int inf = 0x3f3f3f3f;
const int maxn = + ;
struct Node{
int dp[][];
}tree[maxn << ];
int n, q;
char ch[maxn];
map<char, int> id; inline void init(Node &t){
for (int i = ; i < ; i++)
for (int j = ; j < ; j++)
t.dp[i][j] = inf;
} Node Merge(Node a, Node b){
Node tmp; init(tmp);
for (int i = ; i <= ; i++)
for (int j = i; j <= ; j++)
for (int k = i; k <= j; k++)
tmp.dp[i][j] = min(tmp.dp[i][j], a.dp[i][k] + b.dp[k][j]);
return tmp;
} void display(Node t){
for (int i = ; i < ; i++){
for (int j = ; j < ; j++)
printf("%d ", t.dp[i][j]);
cout << endl;
}
} void buildtree(int l, int r, int o){
if (l == r){
init(tree[o]);
for (int i = ; i < ; i++)
tree[o].dp[i][i] = ;
int pos = id[ch[l]];
if (pos <= ) tree[o].dp[pos][pos] = , tree[o].dp[pos][pos + ] = ;
if (pos == ) tree[o].dp[][] = tree[o].dp[][] = ;
return ;
}
int mid = (l + r) / ;
if (l <= mid) buildtree(l, mid, o << );
if (r > mid) buildtree(mid + , r, o << | );
tree[o] = Merge(tree[o << ], tree[o << | ]);
//display(tree[o]);
} Node ans;
void query(int ql, int qr, int l, int r, int o){
if (ql <= l && qr >= r) {
if (ql == l) ans = tree[o];
else ans = Merge(ans, tree[o]);
return ;
}
int mid = (l + r) / ;
if (ql <= mid) query(ql, qr, l, mid, o << );
if (qr > mid) query(ql, qr, mid + , r, o << | );
} int main(){
int cnt = ;
id[''] = , id[''] = , id[''] = , id[''] = , id[''] = ;
for (char i = ''; i <= ''; i++) if(id.count(i) == ) id[i] = ++cnt;
cin >> n >> q;
scanf("%s", ch + );
buildtree(, n, );
for (int i = ; i <= q; i++){
int ql, qr; scanf("%d%d", &ql, &qr);
init(ans);
query(ql, qr, , n, );
if (ans.dp[][] >= inf) puts("-1");
else printf("%d\n", ans.dp[][]);
}
return ;
}

关键:线段树合并