題意：有兩個序列，序列中數字$\in\{-1,0,1\}$

有兩個指針，初始時分別指向兩個序列的開始位置，有一個初始為$0$的數$a$，重復以下過程直到兩個指針都指向序列末尾后

如果一個指針指向末尾后，那么移動另一個指針

否則如果$a>0$，隨機移動一個指針

否則如果至少一個指針指向$1$，隨機移動一個指向$1$的指針

否則隨機移動一個指針

每移動一個指針，就把這個指針指向的數加到$a$上

問有多少種填$0$為$\pm1$的方法使得任何時候都有$a\geq0$

?

首先是對填好的序列進行判定，在兩個序列中分別找到以$-1$結尾的最小前綴和$s_a,s_b$（如果序列全為$1$就選擇總和），如果兩個序列都滿足這個最小前綴和$\ne$總和，那么條件是$s_a+s_b\geq-1$（因為兩個$-1$后面一定都緊跟著一個$1$，而后面的前綴和不會更小，所以可以滿足），否則需要滿足$s_a+s_b\geq0$（一個序列的指針已經到了末尾后，只能被強迫移動另一個指針）

現在要DP，正著DP很困難，考慮倒著DP，這樣每次只會增加一個小前綴

設$f_{i,j,k}$表示填完$[i,n]$，這些位置相對于$i$的前綴和中，以$-1$結尾的最小前綴和$=j$的方案數，$k$表示$j$是否等于總和

如果$i-1$位可以填$1$，那么有$f_{i,j,0}\rightarrow f_{i-1,j+1,0},f_{i,j,1}\rightarrow f_{i-1,j+1,1}$，因為在最前面加一個$1$并不改變原來的最小前綴和

如果$i-1$位可以填$-1$，那么有$f_{i,j,0}\rightarrow f_{i-1,\min(-1,j-1),0},f_{i,j,1}\rightarrow f_{i-1,\min(-1,j-1),[j\le0]}$，因為增加了一個值為$-1$的前綴和，所以原來$j>0$且最小前綴和$=j$的方案會變為最小前綴和$=-1\ne j-1$

對兩個序列分別DP后直接統計答案即可

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; typedef long long ll; typedef int pr[2]; const int mod=998244353; int mul(int a,int b){return(ll)a*b%mod;} void inc(int&a,int b){(a+=b)>=mod?a-=mod:0;} struct str{char s[5010];int n;pr _f[10010],_g[10010],*f=_f+5000,*g=_g+5000;void work(){int i,j;scanf("%s",s+1);n=strlen(s+1);f[0][1]=1;for(i=n;i>0;i--){memset(_g,0,sizeof(_g));for(j=-n;j<=n;j++){if(s[i]!='P'){//+inc(g[j+1][0],f[j][0]);inc(g[j+1][1],f[j][1]);}if(s[i]!='V'){//-inc(g[min(-1,j-1)][0],f[j][0]);inc(g[min(-1,j-1)][j<=0],f[j][1]);}}memcpy(_f,_g,sizeof(_g));}} }a,b; int main(){int i,j,s;a.work();b.work();s=0;for(i=-a.n;i<=a.n;i++){for(j=-b.n;j<=b.n;j++){if(i+j>=-1)inc(s,mul(a.f[i][0],b.f[j][0]));if(i+j>=0){inc(s,mul(a.f[i][0],b.f[j][1]));inc(s,mul(a.f[i][1],b.f[j][0]));inc(s,mul(a.f[i][1],b.f[j][1]));}}}printf("%d",s); }

轉載于:https://www.cnblogs.com/jefflyy/p/10193989.html

總結

以上是生活随笔為你收集整理的[xsy3343]程序锁的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。