【bzoj2272】[Usaco2011 Feb]Cowlphabet 奶牛文字 dp
题目描述
Like all bovines, Farmer John's cows speak the peculiar 'Cow'language. Like so many languages, each word in this language comprisesa sequence of upper and lowercase letters (A-Z and a-z). A wordis valid if and only if each ordered pair of adjacent letters inthe word is a valid pair.
Farmer John, ever worried that his cows are plotting against him,recently tried to eavesdrop on their conversation. He overheard one word before the cows noticed his presence. The Cow language isspoken so quickly, and its sounds are so strange, that all that Farmer John was able to perceive was the total number of uppercaseletters, U (1 <= U <= 250) and the total number of lowercaseletters, L (1 <= L <= 250) in the word.
Farmer John knows all P (1 <= P <= 200) valid ordered pairs of adjacent letters. He wishes to know how many different validwords are consistent with his limited data. However, sincethis number may be very large, he only needs the value modulo97654321.
约翰的奶牛讲的是别人听不懂的“牛语”。牛语使用的字母就是英文字母,有大小写之分。牛语中存在P个合法的词素,每个词素都由两个字母组成。牛语的单词是由字母组成的序列,一个单词是有意义的充要条件是任意相邻的字母都是合法的词素。
输入
* Line 1: Three space-separated integers: U, L and P
* Lines 2..P+1: Two letters (each of which may be uppercase orlowercase), representing one valid ordered pair of adjacentletters in Cow.
第一行:三个用空格隔开的整数:U,L和P,1≤U.L≤250,1≤P<=200
第二行到P+1行:第i+l有两个字母,表示第i个词素,没有两个词素是完全相同的
输出
* Line 1: A single integer, the number of valid words consistent withFarmer John's data mod 97654321.
单个整数,表示符合条件的单词数量除以97654321的余数
样例输入
2 2 7
AB
ab
BA
ba
Aa
Bb
bB
样例输出
7
题解
dp
f[i][j][k]表示使用i个大写字母,j个小写字母,最后一个字母是k的情况数。
注意取模。
#include <cstdio>
#define MOD 97654321
int x[210] , y[210] , f[260][260][60];
char str[5];
int getnum(char ch)
{
return ch >= 'A' && ch <= 'Z' ? ch - 'A' : ch - 'a' + 26;
}
int main()
{
int u , l , p , i , j , k , ans = 0;
scanf("%d%d%d" , &u , &l , &p);
for(i = 1 ; i <= p ; i ++ )
scanf("%s" , str) , x[i] = getnum(str[0]) , y[i] = getnum(str[1]);
for(i = 0 ; i < 26 ; i ++ ) f[1][0][i] = 1;
for(i = 26 ; i < 52 ; i ++ ) f[0][1][i] = 1;
for(i = 2 ; i <= u + l ; i ++ )
{
for(j = 0 ; j <= i && j <= u ; j ++ )
{
for(k = 1 ; k <= p ; k ++ )
{
if(y[k] < 26 && j > 0)
f[j][i - j][y[k]] = (f[j][i - j][y[k]] + f[j - 1][i - j][x[k]]) % MOD;
if(y[k] >= 26 && i - j > 0)
f[j][i - j][y[k]] = (f[j][i - j][y[k]] + f[j][i - j - 1][x[k]]) % MOD;
}
}
}
for(i = 0 ; i < 52 ; i ++ )
ans = (ans + f[u][l][i]) % MOD;
printf("%d\n" , ans);
return 0;
}
最新文章
- JS实现登陆验证的主要代码及思路
- ZOJ 3820 Building Fire Stations 求中点+树的直径+BFS
- 打包Android:Error building Player: CommandInvokationFailure
- Ubuntu 11.10升级Ruby (1.8.7 -->; 1.9.3或者其他任意版本)
- 性能测试_响应时间、并发、RPS的关系
- php 错误信息配置
- Isim你不得不知道的技巧(整理)
- 当程序遇到 throw后的处理
- DedeCMS安装及目录结构
- w2wp.exe 已附加有调试器,但没有将该调试器配置为调试此未经处理的异常
- 射频识别技术漫谈(25)——Felica简介
- C++笔记007:易犯错误模型——类中为什么需要成员函数
- BZOJ_4325_NOIP2015 斗地主_DFS
- PCB Mark点相关
- 加固后,上传play store, 在 google play store 下载应用安装后,打开签名校验失败
- vue(四)-vuex与组件联合使用
- JVM体系结构概述
- Match-----Gray-value-----基于灰度值的模板匹配
- No service of type Factory<;LoggingManagerInternal>; available in ProjectScopeService
- 创建Ajax对象
热门文章
- CodingLabs - MySQL索引背后的数据结构及算法原理
- 绝地求生大逃杀BE启动失败,应用程序无法正常启动
- 「日常训练&;知识学习」单调栈
- jdk从1.8换成1.7后,查看版本还是1.8解决方法
- python程序设计——文件操作
- c字符指针与字符数组的区别
- CTC (Connectionist Temporal Classification) 算法原理
- Trie 树——搜索关键词提示
- LeetCode 144 ——二叉树的前序遍历
- LeetCode - 136. Single Number - ( C++ ) - 解题报告 - 位运算思路 xor