HDU 5642 King's Order 动态规划
King's Order
题目连接:
http://acm.hdu.edu.cn/showproblem.php?pid=5642
Description
After the king's speech , everyone is encouraged. But the war is not over. The king needs to give orders from time to time. But sometimes he can not speak things well. So in his order there are some ones like this: "Let the group-p-p three come to me". As you can see letter 'p' repeats for 3 times. Poor king!
Now , it is war time , because of the spies from enemies , sometimes it is pretty hard for the general to tell which orders come from the king. But fortunately the general know how the king speaks: the king never repeats a letter for more than 3 times continually .And only this kind of order is legal. For example , the order: "Let the group-p-p-p three come to me" can never come from the king. While the order:" Let the group-p three come to me" is a legal statement.
The general wants to know how many legal orders that has the length of n
To make it simple , only lower case English Letters can appear in king's order , and please output the answer modulo 1000000007
We regard two strings are the same if and only if each charactor is the same place of these two strings are the same.
Input
The first line contains a number T(T≤10)——The number of the testcases.
For each testcase, the first line and the only line contains a positive number n(n≤2000).
Output
For each testcase, print a single number as the answer.
Sample Input
2
2
4
Sample Output
676
456950
hint:
All the order that has length 2 are legal. So the answer is 26*26.
For the order that has length 4. The illegal order are : "aaaa" , "bbbb"…….."zzzz" 26 orders in total. So the answer for n == 4 is 26^4-26 = 456950
hint:
For the first testcase you can divide the into one cake of \(2\times2\) , 2 cakes of \(1\times 1\)
Hint
题意
问你长度为n的字符串,只含有小写字母。
没有超过3个连续相同。
问你这个字符串一共有多少种。
题解:
dp[i][j]表示第i个位置,当前连续长度为j的方案数。
然后转移就好了。
可以直接预处理出来。
代码
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<cstring>
using namespace std;
const int mod = 1e9+7;
const int maxn = 2000+7;
long long dp[maxn][4];
void pre()
{
dp[1][1]=26;
for(int i=1;i<=2000;i++)
{
for(int j=1;j<=3;j++)
{
if(dp[i][j])
{
if(j!=3)dp[i+1][j+1]=(dp[i][j]+dp[i+1][j+1])%mod;
dp[i+1][1]=(dp[i+1][1]+dp[i][j]*25)%mod;
}
}
}
}
void solve()
{
int n;scanf("%d",&n);
long long ans = 0;
for(int i=1;i<=3;i++)
ans=(ans+dp[n][i])%mod;
cout<<ans<<endl;
}
int main()
{
int t;scanf("%d",&t);
pre();
while(t--)solve();
return 0;
}
最新文章
- JavaScript和JQuery好书推荐
- js读取解析JSON类型数据(转)
- Tmux
- javac 错误: 编码GBK的不可映射字符
- 使用ContentObserve监听用户发出的短信
- 学会使用Ogitor
- iOS App中数据加载的6种方式
- Svn 的 Update 与Maven 的update project 作用有什么区别
- React Native中常见操作
- ACM OJ Collection
- Zookeeper为什么总是奇数个
- MyEclipse 在loading workbench 启动卡死
- C语言两个libxml2库使用的问题
- Redmine管理项目1-自定义属性
- 23. leetcode 169. Majority Element
- vue学习笔记(三)——目录结构介绍
- Android的AIDL机制
- sed (未完,待续)
- suse11安装mysql5.7
- mysql数据库的卸载