佚名通过本文主要向大家介绍了codeforces,codeforces验证码,codeforces.com,codeforces怎么注册,codeforces是什么等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
问题：Codeforces:吉他手问题
描述:
解决方案1:
描述:
【题目描述】
音乐是储存记忆最好的方式，你的一切于我来说，始于音符，终于和弦。
作为一名专业的吉他手，Jzzhu经常在空闲的时候来研究和弦的构成。
他把一个和弦定义为包含n个音符的序列，而且每个音符都有一个频率值。为了使音乐更
加动听，Jzzhu规定，一个和弦里第i个音符的频率值必须小于第i+2(如果存在）和第
i+3(如果存在）个音符的频率值。
而且对于一个包含n个音符的和弦，每个音符的频率值都是一个属于[1,n]的正整数。
现在Jzzhu想知道给定一个正整数n，共有多少种不同的和弦呢。
注意两个和弦不同，当且仅当存在一个位置，这两个和弦此位置上的音符频率值不相同。
【输入格式】
输入文件名为 guitar.in
一个正整数n
【输出格式】
输出文件名为 guitar.in
一行一个数，表示不同和弦的种类数。结果对4294967296取模。
【输入输出样例】
guitar.in
3
guitar.out
9
【数据范围】
对于20%的数据，1 <= n <= 50
对于50%的数据，1 <= n <= 300
对于100%的数据，1 <= n <= 1000
解决方案1:
这题需要使用动态规划
设一数组dp[i][j]表示前i个中不超过j的情况有几个。
状态转移方程dp[i][j]=dp[i][j-1]+dp[i-1][j]+dp[i-2][1..(i-1)];
现在解释：第一部分dp[i][j-1]表示没有达到j存在的情况
第二部分dp[i-1][j]表示j在i-1上的情况(这种情况下并不包括i和i-1都是j的情况)。
第三部分dp[i-2][1..(i-1)]表示j在i-1上的情况(此时类似于枚举第i个是多少，最多是j最少是2，于是i-2最多是i-1最少是1)
对于的三部分可以使用前缀数组优化求和。