Codeforces:吉他手问题

Question

【题目描述】
音乐是储存记忆最好的方式，你的一切于我来说，始于音符，终于和弦。
作为一名专业的吉他手，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

Answer 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)

对于的三部分可以使用前缀数组优化求和。