hdu1502 Regular Words--DP&大数问题-白红宇的个人博客

发布日期：2021-10-03 20:32:05 浏览次数：3 分类：技术文章

本文共 1009 字，大约阅读时间需要 3 分钟。

原题链接：

一：原题内容

Problem Description

Consider words of length 3n over alphabet {A, B, C} . Denote the number of occurences of A in a word a as A(a) , analogously let the number of occurences of B be denoted as B(a), and the number of occurenced of C as C(a) .

Let us call the word w regular if the following conditions are satisfied:

A(w)=B(w)=C(w) ;

if c is a prefix of w , then A(c)>= B(c) >= C(c) .

For example, if n = 2 there are 5 regular words: AABBCC , AABCBC , ABABCC , ABACBC and ABCABC .

Regular words in some sense generalize regular brackets sequences (if we consider two-letter alphabet and put similar conditions on regular words, they represent regular brackets sequences).

Given n , find the number of regular words.

Input

There are mutiple cases in the input file.

Each case contains n (0 <= n <= 60 ).

There is an empty line after each case.

Output

Output the number of regular words of length 3n .

There should be am empty line after each case.

Sample Input

Sample Output

二：分析理解

和

三：AC代码

转载地址：https://blog.csdn.net/LaoJiu_/article/details/51001961 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：hdu2544 最短路--单源最短路径

下一篇：hdu1227 Fast Food--DP

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章