http://www.lydsy.com/JudgeOnline/problem.php?id=3802
dp[i][0/1/2/3] 表示前i个字母，第1、2个字符串，第2、3个字符串的关系分别为 < < , = < , < = , = =
枚举前i-1个字母 构成的关系
再枚举3个字符串的字母 转移
时间复杂度为 O（N* 26^3）
优化转移：
转移都是dp[i-1][0/1/2/3]-->dp[i][0/1/2/3]
预处理出f[i][j][k][s:0~3][t:0~3] 表示前面字母构成的字符串的关系为s，3个字符串分别加上1个字母i、j、k后转移到关系t的方案数
转移的时候不枚举3个字符串的字母，枚举新的关系0~3
直接用f数组转移
#include<cstdio>
#include<cstring> using namespace std; #define N 1000002 const int mod=1e9+; char s1[N],s2[N],s3[N]; int f[][][][][];
int dp[N][];
//0:i<j<k 1:i=j<k 2:i<j=k 3:i=j=k void pre()
{
int li,ri,lj,rj,lk,rk;
int t;
for(int i=;i<=;++i)
for(int j=;j<=;++j)
for(int k=;k<=;++k)
{
if(i==) li=,ri=;
else li=ri=i;
if(j==) lj=,rj=;
else lj=rj=j;
if(k==) lk=,rk=;
else lk=rk=k;
for(int ci=li;ci<=ri;++ci)
for(int cj=lj;cj<=rj;++cj)
for(int ck=lk;ck<=rk;++ck)
for(int s=;s<=;++s)
{
if(!s) t=;
else if(s==)
{
if(ci==cj) t=;
else if(ci<cj) t=;
else t=-;
}
else if(s==)
{
if(cj==ck) t=;
else if(cj<ck) t=;
else t=-;
}
else
{
if(ci>cj || ci>ck || cj>ck) t=-;
else if(ci<cj && cj<ck) t=;
else if(ci==cj && cj<ck) t=;
else if(ci<cj && cj==ck) t=;
else t=;
}
if(t>=) f[i][j][k][s][t]++;
}
}
} int main()
{
pre();
int T;
scanf("%d",&T);
int l1,l2,l3,len;
int x,y,z;
while(T--)
{
scanf("%s",s1+);
scanf("%s",s2+);
scanf("%s",s3+);
l1=strlen(s1+);
len=l1;
l2=strlen(s2+);
if(l2>len) len=l2;
l3=strlen(s3+);
if(l3>len) len=l3;
while(l1!=len) s1[++l1]='a'-;
while(l2!=len) s2[++l2]='a'-;
while(l3!=len) s3[++l3]='a'-;
for(int i=;i<=len;++i)
for(int j=;j<=;++j)
dp[i][j]=;
dp[][]=;
for(int i=;i<=len;++i)
{
x=s1[i]-'a'+;
if(x<) x=;
y=s2[i]-'a'+;
if(y<) y=;
z=s3[i]-'a'+;
if(z<) z=;
for(int j=;j<=;++j)
if(dp[i-][j])
for(int k=;k<=;++k)
dp[i][k]=(dp[i][k]+(long long)dp[i-][j]*f[x][y][z][j][k]%mod)%mod;
}
printf("%d\n",dp[len][]);
}
}
3802: Vocabulary
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 185 Solved: 68
[Submit][Status][Discuss]
Description
给你三个字符串，这些字符串有些单词模糊不可认了，用"?"来代表。
现在你可以用任意英文小写字母来代表它们。要求是使得给定的三个字符串中
所有的"?"被你认定的字母代替后，各不相同且按字典序出现。问有多少种方式。
Input
先给出一个数字N，代表数据组数。
接下来3*N行，每行给出一个字符串。长度<=1000 000
Output
输出结果 Mod 10^9+9
Sample Input
3
?heoret?cal
c?mputer
?cience
jagiellonia
?niversity
kra?ow
?
b
c
?heoret?cal
c?mputer
?cience
jagiellonia
?niversity
kra?ow
?
b
c
Sample Output
42562
52
1
52
1