【线段树上dp】Codeforces 750 E New Year and Old Subsequence

线段树上dp】Codeforces 750 E New Year and Old Subsequence"/>

【线段树上dp】Codeforces 750 E New Year and Old Subsequence

题目链接：

题意

给一个1~n的数字串，每次询问在区间【l,r】之间至少要删除几个字符使得剩下的的数中有2017但是没有2016

思路

我们会发现，这个问题由两个子问题构成：

1. 对于一个串，我们要如何来计算需要删除几个字符
2. 如何将这个问题转化成一个区间查询的问题

问题1解决

1. 显然这个问题要用dp来解决，但是怎么解决呢
2. 这个地方用到了矩阵和floyd最短路的转移
3. 假设说这个问题求的是1~n的字符串的转移，那么代码如下

/*在这里，我们定义空状态为0,2为1,20为2,201为3,2017为4
mat[x]的矩阵m[i][j]表示当前在x位置上要从i状态转移到j状态需要删除多少字符*/struct Matrice
{int m[5][5];void init(){memset(m,inf,sizeof(m));}Matrice operator *(const Matrice a) const{Matrice res;res.init();/*floyd最短路转移*/for(int k=0;k<5;k++)for(int i=0;i<5;i++)for(int j=0;j<5;j++)res.m[i][j]=min(res.m[i][j],m[i][k]+a.m[k][j]);return res;}
}mat[maxn],ans;void cal(int x)
{mat[x].init();for(int i=0;i<5;i++) mat[x].m[i][i]=0;if(a[x]==2){mat[x].m[0][0]=1;//从空状态到空状态需要把当前的a[x]删掉，所以转移所需代价为1mat[x].m[0][1]=0;//从空状态到1状态只需把当前的a[x]加上即可}/*下面如上*/if(a[x]==0){mat[x].m[1][1]=1;mat[x].m[1][2]=0;}if(a[x]==1){mat[x].m[2][2]=1;mat[x].m[2][3]=0;}if(a[x]==7){mat[x].m[3][3]=1;mat[x].m[3][4]=0;}if(a[x]==6){mat[x].m[3][3]=1;//2016这种情况是不允许出现的，所以它只能从3转移到3mat[x].m[4][4]=1;//因为上不去了嘛，所以只能从4到4了/*这个地方之前想的时候会有一个疑问，就是说当串为20176的时候，感觉是不是会把6删掉这样一来，答案会不会达不到最小，然后在问了学姐以后意识到这个cal处理的只是每一个字符的矩阵，对于7来说，它的状态是0，他们每一个字符的矩阵是独立的，求最短的这个操作只有进行了floyd以后才可以求到最短，现在只是建了一条4到4的路而已我太菜了qaq*/}
}void solve()
{for(int i=1;i<=n;i++) scanf("%1d",&a[i]);for(int i=1;i<=n;i++)cal(i);ans.init();for(int i=0;i<5;i++) ans.m[i][i]=0;for(int i=1;i<=n;i++)ans=ans*mat[i]; //从前往后一个一个转移printf("%d\n",dp[0][4]<=n?dp[0][4]:-1);//如果从1到n无法转移到所需状态，dp[0][4]==inf
}

问题2

1. 如何求一段区间，我们发现，前缀和是完不成这个任务的，因为乘完了以后不可能再除回去
2. 我们选择了线段树这个工具
3. 我们进行建树操作，将几个矩阵并起来，实现logn的区间查询，就是加了一个普通的建树操作和区间查询操作，只不过这边建树的时候是采取了floyd矩阵转移的方式

完整代码如下

#include <iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<map>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<stack>using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const int maxn=200005;
const int inf=0x3f3f3f3f;
/*在这里，我们定义空状态为0,2为1,20为2,201为3,2017为4
mat[x]的矩阵m[i][j]表示当前在x位置上要从i状态转移到j状态需要删除多少字符*/struct Matrice
{int m[5][5];void init(){memset(m,inf,sizeof(m));}Matrice operator *(const Matrice a) const{Matrice res;res.init();/*floyd最短路转移*/for(int k=0;k<5;k++)for(int i=0;i<5;i++)for(int j=0;j<5;j++)res.m[i][j]=min(res.m[i][j],m[i][k]+a.m[k][j]);return res;}
}mat[maxn<<2],ans;
int a[maxn],n,m;void cal(int x,int root)
{mat[root].init();for(int i=0;i<5;i++) mat[root].m[i][i]=0;if(a[x]==2){mat[root].m[0][0]=1;//从空状态到空状态需要把当前的a[x]删掉，所以转移所需代价为1mat[root].m[0][1]=0;//从空状态到1状态只需把当前的a[x]加上即可}/*下面如上*/if(a[x]==0){mat[root].m[1][1]=1;mat[root].m[1][2]=0;}if(a[x]==1){mat[root].m[2][2]=1;mat[root].m[2][3]=0;}if(a[x]==7){mat[root].m[3][3]=1;mat[root].m[3][4]=0;}if(a[x]==6){mat[root].m[3][3]=1;//2016这种情况是不允许出现的，所以它只能从3转移到3mat[root].m[4][4]=1;//因为上不去了嘛，所以只能从4到4了/*这个地方之前想的时候会有一个疑问，就是说当串为20176的时候，感觉是不是会把6删掉这样一来，答案会不会达不到最小，然后在问了学姐以后意识到这个cal处理的只是每一个字符的矩阵，对于7来说，它的状态是0，他们每一个字符的矩阵是独立的，求最短的这个操作只有进行了floyd以后才可以求到最短，现在只是建了一条4到4的路而已我太菜了qaq*/}
}void build(int l,int r,int root)
{if(l==r){cal(l,root);return ;}int mid=l+r>>1;build(l,mid,root<<1);build(mid+1,r,root<<1|1);mat[root]=mat[root<<1]*mat[root<<1|1];
}/*线段树区间查询*/
void query(int root,int l,int r,int ql,int qr)
{if(l>=ql&&r<=qr){ans=ans*mat[root];return ;}int mid=r+l>>1;if(mid>=ql) query(root<<1,l,mid,ql,qr);if(mid<qr) query(root<<1|1,mid+1,r,ql,qr);
}void solve()
{for(int i=1;i<=n;i++) scanf("%1d",&a[i]);build(1,n,1);int l,r;while(m--){ans.init();for(int i=0;i<5;i++) ans.m[i][i]=0;scanf("%d%d",&l,&r);query(1,1,n,l,r);printf("%d\n",ans.m[0][4]<=n?ans.m[0][4]:-1);//如果从1到n无法转移到所需状态，dp[0][4]==inf}
}int main()
{scanf("%d%d",&n,&m);solve();return 0;
}

综上所述，我太菜了qaq