題目鏈接

題意：

一個"10"能被"0"替換，一個"01"能被"1"替換，給你一個長度為n的01串，問有多少子串能通過變換成為長度為1的串

分析：

首先想到的就是DP了，f[i][0]表示的是以第i個元素結(jié)尾的能變換成"0"這個字母的所有方案數(shù)，f[i][1]表示的是以第i個元素結(jié)尾的能變換成"1"這個字母的所有方案數(shù)，那么當?shù)趇個元素是’0’時，f[i][0]能從f[i-1][1]來轉(zhuǎn)移過來，而且還要+1，因為它本身就算是一個，這樣子得出的結(jié)果是少的，因為000這種和111這種沒算進去，f[i][0]的更新110這種也要算進去的，那么就把fi][2]表示成以第i個元素結(jié)尾，能形成00這種結(jié)尾的方案數(shù)，把f[i][3]表示成能形成11這種結(jié)尾的方案數(shù)，具體請看代碼：

#include<bits/stdc++.h> using namespace std; const int N = 200010; char s[N]; long long f[N][4]; void solve(){int n;scanf("%d%s",&n,s+1);long long ans = 0;for(int i=1;i<=n;i++){if(s[i] == '0'){f[i][0] = f[i-1][1] + 1 + f[i-1][3];f[i][1] = 0;f[i][2] = f[i-1][0] + f[i-1][2];f[i][3] = 0;}else{f[i][0] = 0;f[i][1] = f[i-1][0] + 1 + f[i-1][2];f[i][2] = 0;f[i][3] = f[i-1][1] + f[i-1][3];}ans += f[i][0] + f[i][1];}cout<<ans<<endl; } int main(){int _;scanf("%d",&_);while(_--) solve();return 0; }

總結(jié)

以上是生活随笔為你收集整理的【codeforces round#800 B. Paranoid String】DP的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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