传送门

分析

将所有字母分别转化为1~26,之后将字符串的空位补全为0,?设为-1,我们设dp[p][c][le][ri]表示考虑le到ri个字符串且从第p位开始考虑,这一位最小填c的方案数,具体转移见代码。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
const long long mod = ;
#define add(x,y) x=(x+y)%mod
long long dp[][][][];
int len[],n,m,a[][];
char s[][];
inline long long getdp(int p,int c,int le,int ri){
if(c>)return ;
if(p>m)return le==ri;
if(dp[p][c][le][ri]!=-)return dp[p][c][le][ri];
dp[p][c][le][ri]=getdp(p,c+,le,ri);
for(int i=le;i<=ri;i++){
if(!c&&a[i][p]==-)break;
if(a[i][p]>=&&a[i][p]!=c)break;
long long t=getdp(p+,,le,i);
if(i!=ri)t=t*getdp(p,c+,i+,ri)%mod;
add(dp[p][c][le][ri],t);
}
return dp[p][c][le][ri];
}
int main(){
int i,j,k;
scanf("%d",&n);
memset(dp,-,sizeof(dp));
for(i=;i<=n;i++){
scanf("%s",s[i]);
len[i]=strlen(s[i]);
m=max(m,len[i]);
}
for(i=;i<=n;i++)
for(j=;j<=m;j++)
if(j>len[i])a[i][j]=;
else if(s[i][j-]=='?')a[i][j]=-;
else a[i][j]=s[i][j-]-'a'+;
printf("%lld\n",getdp(,,,n));
return ;
}

最新文章

  1. c/C++二进制运算符
  2. ClearContainer 网络部分源码分析
  3. Majority Element II
  4. 关于margin的问题
  5. mongoosejs model mapping to collection name
  6. 【BZOJ 3143】【Hnoi2013】游走 期望+高斯消元
  7. meta 标签属性(网站兼容与优化需要)
  8. 一个Web页面的生命周期 ,面试常常被问到
  9. 使用Bundle在Activity之间交换数据
  10. 201521123014 《Java程序设计》第12周学习总结
  11. 从操作系统内核看Java非阻塞IO事件检测
  12. 【手记】解决EXCEL跑SQL遇“查询无法运行或数据库表无法打开...”
  13. 融云通信云发力教育行业 助在线教育&quot;风口&quot;继续腾云
  14. js配置文件路径和项目目录文件夹位置的一致性
  15. 关于Chrome 67 以后版本无法离线安装扩展的解决方法
  16. 第73节:Java中的HTTPServletReauest和HTTPServletResponse
  17. CentOS 7 使用SVN+Apache搭建版本控制服务器
  18. 618大促微服务、web、redis等的超时时间
  19. [No0000131]WCF压缩传输方案整理
  20. 矩形嵌套(dp)

热门文章

  1. 服务器端使用DeferredResult异步推送技术
  2. nyoj-115-城市平乱(dijkstra算法)
  3. Smarty的模板中不允许PHP的代码?
  4. LCD升压反压驱动电路
  5. ShadowGun 图形技术分析
  6. 批处理执行多个SQL文件到oracle
  7. OTL调用Oracle存储过程
  8. BZOJ3170:[TJOI2013]松鼠聚会
  9. unix下网络编程之I/O复用(四)
  10. Qt中如何用QImage::Format_Indexed8表示灰度图