HDU 5642 King's Order dp
2024-10-19 22:42:04
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=5642
King's Order
Accepts: 381
Submissions: 1361
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
国王演讲后士气大增,但此时战争还没有结束,国王时不时要下发命令。 由于国王的口吃并没有治愈,所以传令中可能出现:“让第三军-军-军,到前线去” 这样的命令。由于大洋国在军队中安插了间谍 , 战事紧急,很多时候前线的指挥官不能分清哪些命令真正来自国王。但国王的命令有一个特点,他每次连续重复的字符最多 33 次. 所以说他的命令中没有:“让第三军-军-军-军 , 到前线去”,但是可以有 :“让第三军-军 , 到前线去” 。 此时将军找到了你,你需要告诉他,给定命令的长度长度为 nn,有多少种不同的命令可以是国王发出的 。(也就是求长度为 nn 的合格字符串的个数)当然,国王可能说出一句话没有犯任何口吃,就像他那次演讲一样。 为了简化答案,国王的命令中只含有小写英文字母,且对答案输出模 10000000071000000007。 我们认为两个命令如果完全相同那么这两个字符串逐个比较就完全相同。
输入描述
第一行一个整数表示测试组数:T(T \le10)T(T≤10)。 每组数据占一行,每行一个正整数 n(n \le 2000)n(n≤2000) 表示字符串的长度。
输出描述
共 TT 行,每行一个整数表示合法的命令数量。
输入样例
2 2 4
输出样例
676 456950
Hint
两个中没有不符合要求的,所以答案为 26\times 26 = 67626×26=676 四个不符合要求的只有 `aaaa` `bbbb` ... `zzzz`总共 26 个 那么答案就是: 26^4-26 = 456950264−26=456950
题解:
方法一:
dp[i][j]表示长度为i以字母j+'a'结尾的所有合法情况,现在我们先考虑所有情况再减去那些非法情况(以连续四个j结尾的状态为非法状态 ,超过四个j的之前一定已经考虑过了,这里不能再考虑进去)所以先预处理出i<=4的值,对于i>5,有如下转移方程:
dp[i][j]=∑dp[i-1][k]-( ∑dp[i-4][k](k!=j) )
代码1:
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 typedef long long LL;
5 using namespace std;
6
7
8 const int maxn=+;
9 const int mod=1e9+;
int dp[maxn][];
int n;
void init(){
memset(dp,,sizeof(dp));
}
int main(){
int tc;
scanf("%d",&tc);
while(tc--){
init();
scanf("%d",&n);
for(int j=;j<;j++) dp[][j]=;
for(int i=;i<=n;i++){
int sum=;
for(int j=;j<;j++){
sum+=dp[i-][j];
sum%=mod;
}
for(int j=;j<;j++){
dp[i][j]=sum;
if(i==){
dp[i][j]=(dp[i][j]-dp[i-][j]+mod)%mod;
}
else if(i>){
//tmp记录连续四个j结尾的情况。
int tmp=;
for(int k=;k<;k++){
if(k==j) continue;
tmp+=dp[i-][k];
tmp%=mod;
}
dp[i][j]=(dp[i][j]-tmp+mod)%mod;
}
}
}
int ans=;
for(int i=;i<;i++) {
ans+=dp[n][i];
ans%=mod;
}
printf("%d\n",ans);
}
return ;
}
最新文章
- c# .Net :Excel NPOI导入导出操作教程之数据库表信息数据导出到一个Excel文件并写到磁盘示例分享
- SVN 删除误上传到服务器的文件
- 三表联查,这是我目前写过的最长的sql语句,嗯嗯,果然遇到问题才能让我更快成长,更复杂的语句也有了一些心得了
- IE兼容forEach/map/every/some/indexOf/filter
- crossplatform---bower解决js的依赖管理
- submit回车提交影响
- Linux Shell脚本Ldd命令原理及使用方法
- 轻松实现HTML5时钟(分享下自己对canvas的理解,原来没你想像的那么难哦)
- javascriptDOM编程艺术_学习笔记_知识点 DOM
- 【QT相关】类头文件解读、QT编辑模式、读取text文本
- The Go Programming Language. Notes.
- AMDP + XLSX Workbench 报表开发模式
- python:print输出内容大拼接,重新认识 + 和 ,
- 使用 vue-cli-service inspect 来查看一个 Vue CLI 3 项目的 webpack 配置信息(包括:development、production)
- 32 bit 与 64 bit 程序(1)如何识别?
- javascript 模拟京东关闭广告栏
- ECNU 3260 - 袋鼠妈妈找孩子
- springMVC源码分析--HttpMessageConverter写write操作(三)
- Kafka开发环境搭建(五)
- python发送GET或POST请求以便干一些趣事