hdu4055 Number String
Number String
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1027 Accepted Submission(s): 448
Your task is as follows: You are given a string describing the signature of many possible permutations, find out how many permutations satisfy this signature.
Note: For any positive integer n, a permutation of n elements is a sequence of length n that contains each of the integers 1 through n exactly once.
Each test case occupies exactly one single line, without leading or trailing spaces.
Proceed to the end of file. The '?' in these strings can be either 'I' or 'D'.
ID
DI
DD
?D
??
2
2
1
3
6
Permutation {1,2,3} has signature "II".
Permutations {1,3,2} and {2,3,1} have signature "ID".
Permutations {3,1,2} and {2,1,3} have signature "DI".
Permutation {3,2,1} has signature "DD".
"?D" can be either "ID" or "DD".
"??" gives all possible permutations of length 3.
#include <iostream>
#include <stdio.h>
#include <string.h>
#define mod 1000000007
using namespace std;
char str[1050];
int dp[1050][1050],sum[1050][1050];
int main()
{
int i,j;
while(scanf("%s",str)!=EOF)
{
memset(dp,0,sizeof(dp));
sum[1][1]=1;
int strnum=strlen(str);
for(i=2;i<=strnum+1;i++)
{
for(j=1;j<=i;j++)
{
if(str[i-2]=='I'||str[i-2]=='?')
{ dp[i][j]=(dp[i][j]+sum[i-1][j-1])%mod;
}
if(str[i-2]=='D'||str[i-2]=='?')
{ dp[i][j]=(dp[i][j]+((sum[i-1][i-1]-sum[i-1][j-1])%mod+mod)%mod)%mod; }
sum[i][j]=(sum[i][j-1]+dp[i][j])%mod;
}
}
printf("%d\n",sum[strnum+1][strnum+1]);
}
return 0;
}
Statistic |
Submit |
Discuss |
Note
最新文章
- 基于STM32Cube的IIC主从通信
- MySQL 常用命令总结
- struts2的拦截器(Interceptor)与过滤器(Filter)
- A Simple MVVM Example[Forward]
- .NET开源工作流RoadFlow-流程设计-流程步骤设置-策略设置
- 总结Allegro元件封装(焊盘)制作方法[修整]
- Java GC 概念摘要
- UVA_Digit Puzzle UVA 12107
- C++教程之autokeyword的使用
- linux几条常用的命令
- HDU - 1907 John 反Nimm博弈
- SpriteBuilder中的粒子系统属性
- 数据库数据迁移 SqlServer复制到mysql
- MSSQL coalesce系统函数简介
- 18春季训练01-3/11 2015 ACM Amman Collegiate Programming Contest
- 【webdriver自动化】Python数据驱动工具DDT
- Android---Hellow World
- 【python】初识python
- Alpha发布评价
- Checkpoint--在Tempdb上的特殊性