【DP】SRM480D1L3 StringDecryption

题意：

定义一种加密方式为： 将原串中，所有连续相同的字符提取出来，替换为：出现次数和原字符： 例如： $11222277$加密后变为： $214227$

现在某个串这样加密了两次，求原串有多少种可能的状态。

---

分析：

首先，考虑一次解密： 有一个很显然的$O(n^2)DP$

定义$DP[i][c]$表示，前i个字符中，最后一个解密的字符为$c$的方案数（即目前以’c’字符结尾）。

转移很显然： $DP[i][c]=\sum DP[j][c^{\prime }](j\le i-2,c̸=c^{\prime })$且由$(S_{j+1}{S}_{j+2}\dots \dots S_{i-1})$所组成的数字不能有前导0

现在再来考虑一次解密后的串长什么样子： $aaa\dots \dots aabbb\dots \dots bbbccc\dots \dots ccddd\dots \dots$（这里用字母代替数字）

简而言之：是由数个相同的字符，与其它部分拼接起来的串。

由于题目给出的加密方式，很显然解密时两个相邻字符不能相同。

这就可以给我们很大的启发：每个连续相同串中，最多划分1次。

因此，可以定义 $DP[i][c][0/1]$表示：在题目给出串的前i个字符，以c结尾，且当前这一区间是否刚好划分完（即在一串相同的字符中，$ddddddddddd$，1表示最后一个d被作为二次解密时的“原字符”，前面视为“出现次数”，0则反之）

现在就可以转移了： 首先，$DP[i][c][0]=DP[j][c][0/1]$ 表示当前从$(S_{j+1}{S}_{j+2}\dots \dots S_{i-1})S_i$这一段完全作为出现次数的一部分（即不在这个区间中划分）

(设$Num=(S_{j+1}{S}_{j+2}\dots \dots S_{i-1})$即从j+1到i-1这段字符) $DP[i][S_i][0]=DP[j][c][0]\ast (Num-1)+DP[j][c][1]\ast (Num-2)$ 一个乘$Num-1$另一个乘$Num-2$取决于能不能划分在第一个字符： 如果之前有数字（状态为0），那么第一个字符就能划分。 如果之前没有数字（状态为1），那么第一个字符就不能划分（因为划分了就没有“出现次数”）

$DP[i][S_i][1]=DP[j][c][0]+DP[j][c][1]$ 这部分比较简单，就是在最后一个位置划分一下就行了。

但是有些情况是非法的，具体看代码

#include<cstring> #include<algorithm> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<iostream> #define SF scanf #define PF printf #define MAXN 510 #define MOD 1000000009 using namespace std; typedef long long ll; ll dp[MAXN][11][2]; string s; int main(){ cin>>s; int n=s.size(); dp[0][10][1]=1; for(int i=1;i<=n;i++){ ll tims=0; ll pw10=1; char lastc=s[i-1]; for(int j=i-2;j>=0;j--){ tims=(tims+pw10*(s[j]-'0'))%MOD; pw10=pw10*10ll%MOD; if(s[j]=='0') continue;//leading zero in first division if(j>0&&s[j-1]==lastc) continue;//overlap for(int k=0;k<11;k++){//add 10 to update from pos_0 for(int flag=0;flag<2;flag++){ if(dp[j][k][flag]==0) continue; if(lastc=='0'&&flag==1)//leading zero in second division continue; dp[i][k][0]=(dp[i][k][0]+dp[j][k][flag])%MOD; if(k!=lastc-'0'){ if(lastc>'0'&&(j<i-2||tims>1))//"j<i-2" to avoid (tims mod 1e9+7) <=1 dp[i][lastc-'0'][0]=(dp[i][lastc-'0'][0]+dp[j][k][flag]*(tims-1ll-flag+MOD)%MOD)%MOD; if(j<i-2||tims>1||flag==0) dp[i][lastc-'0'][1]=(dp[i][lastc-'0'][1]+dp[j][k][flag])%MOD; } } } } } PF("%lld",dp[n][s[n-1]-'0'][1]); }