題目鏈接：點擊查看

題目大意：給出一個長度為n的只由數(shù)字組成的字符串，再給出m個詢問，每次詢問給出閉區(qū)間[l,r]，求區(qū)間內(nèi)想要包含“9102”，但不包含“8102”時需要刪除字母的最小數(shù)目

題目分析：這個題和CF上的一個題目很像，只不過那個題是需要包含2018而不包含2017，乍一看只是年份不一樣，其實還與他的順序有關(guān)，先掛一個大牛的博客：點擊查看

上面的博客中詳細的解釋了2018和2017那道題的做法，在這里我再簡單總結(jié)一下，就是開一個線段樹，每個節(jié)點保存的是一個矩陣，這個矩陣儲存的是轉(zhuǎn)移所需要付出的代價（即最小需要刪除的字母數(shù)量），狀態(tài)是若想要從上一個狀態(tài)轉(zhuǎn)移到當(dāng)前狀態(tài)所需要付出的代價，然后要對矩陣乘法進行重定義，定義為c[i][j]=min(a[i][k]+b[k][j])；說起來可能比較抽象，實際上可以將2018分為五個狀態(tài)：?，2,20,201,2018，分別編號為1,2,3,4,5，共五個狀態(tài)，每一種狀態(tài)都只能由前一種狀態(tài)轉(zhuǎn)移而來，轉(zhuǎn)移也是需要付出相應(yīng)的代價，而到了2017時，只能由201或2018這兩個狀態(tài)轉(zhuǎn)移而來，但題目中不允許出現(xiàn)2017，所以我們需要將最后一位的7刪除，整體就是這么一個轉(zhuǎn)移的思路。

而在這個題目中，給出的字符串是第一個字母不同，我們就會類比到剛才的那個題目中去，我們可以先將字符串翻轉(zhuǎn)一下，然后再將區(qū)間翻轉(zhuǎn)，因為字符串長度為n，所以很容易找到對應(yīng)的關(guān)系，反轉(zhuǎn)前的區(qū)間若是[l,r]，那么反轉(zhuǎn)后的區(qū)間就變成了[n+1-r,n+1-l]，這樣就能對反轉(zhuǎn)的數(shù)組進行上述動態(tài)轉(zhuǎn)移了。

上代碼了：

#include<iostream> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<cstdio> #include<queue> using namespace std; typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e5+100;string str;const int M=5;struct Ma {int a[M][M];Ma(){memset(a,inf,sizeof(a));}Ma operator*(const Ma& b)const{Ma ans;for(int i=0;i<M;i++)for(int j=0;j<M;j++)for(int k=0;k<M;k++)ans.a[i][j]=min(ans.a[i][j],a[i][k]+b.a[k][j]);return ans;} };struct Node {int l,r;Ma a; }tree[N<<2];void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;if(l==r){for(int i=0;i<M;i++)tree[k].a.a[i][i]=0;if(str[l]=='2'){tree[k].a.a[0][0]=1;tree[k].a.a[0][1]=0;}if(str[l]=='0'){tree[k].a.a[1][1]=1;tree[k].a.a[1][2]=0;}if(str[l]=='1'){tree[k].a.a[2][2]=1;tree[k].a.a[2][3]=0;}if(str[l]=='9'){tree[k].a.a[3][3]=1;tree[k].a.a[3][4]=0;}if(str[l]=='8'){tree[k].a.a[3][3]=1;tree[k].a.a[4][4]=1;}return;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);tree[k].a=tree[k<<1].a*tree[k<<1|1].a; }Ma query(int k,int l,int r) {if(tree[k].l>=l&&tree[k].r<=r)return tree[k].a;int mid=tree[k].l+tree[k].r>>1;if(mid>=r)return query(k<<1,l,r);else if(mid<l)return query(k<<1|1,l,r);elsereturn query(k<<1,l,r)*query(k<<1|1,l,r); }int main() {int n,m;while(scanf("%d%d",&n,&m)!=EOF){cin>>str;reverse(str.begin(),str.end());str=" "+str;build(1,1,n);while(m--){int x,y;scanf("%d%d",&x,&y);int l=n+1-y;int r=n+1-x;Ma temp=query(1,l,r);int ans;if(temp.a[0][4]>n)ans=-1;elseans=temp.a[0][4];printf("%d\n",ans);}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的2019ICPC(南昌) - Hello 2019(动态规划+线段树维护矩阵)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。