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 
      
       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 = 200000 + 5;struct Node{    int dp[5][5];}tree[maxn << 2];int n, q;char ch[maxn];map
       
         id;inline void init(Node &t){    for (int i = 0; i < 5; i++)        for (int j = 0; j < 5; j++)            t.dp[i][j] = inf;}Node Merge(Node a, Node b){    Node tmp; init(tmp);    for (int i = 0; i <= 4; i++)        for (int j = i; j <= 4; 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 = 0; i < 5; i++){        for (int j = 0; j < 5; 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 = 0; i < 5; i++)            tree[o].dp[i][i] = 0;        int pos = id[ch[l]];        if (pos <= 3) tree[o].dp[pos][pos] = 1, tree[o].dp[pos][pos + 1] = 0;        if (pos == 4) tree[o].dp[3][3] = tree[o].dp[4][4] = 1;        return ;    }    int mid = (l + r) / 2;    if (l <= mid) buildtree(l, mid, o << 1);    if (r > mid) buildtree(mid + 1, r, o << 1 | 1);    tree[o] = Merge(tree[o << 1], tree[o << 1 | 1]);    //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) / 2;    if (ql <= mid) query(ql, qr, l, mid, o << 1);    if (qr > mid) query(ql, qr, mid + 1, r, o << 1 | 1);}int main(){    int cnt = 4;    id['2'] = 0, id['0'] = 1, id['1'] = 2, id['7'] = 3, id['6'] = 4;    for (char i = '3'; i <= '9'; i++) if(id.count(i) == 0) id[i] = ++cnt;    cin >> n >> q;    scanf("%s", ch + 1);    buildtree(1, n, 1);    for (int i = 1; i <= q; i++){        int ql, qr; scanf("%d%d", &ql, &qr);        init(ans);        query(ql, qr, 1, n, 1);        if (ans.dp[0][4] >= inf) puts("-1");        else printf("%d\n", ans.dp[0][4]);    }    return 0;}
       
      

 

关键：线段树合并