题目链接：http://codeforces.com/problemset/problem/14/E

题意：就是给出n个点要求画出t个波峰和t-1个波谷

很显然要t个波峰和t-1个波谷开始是波动一定是向上的最后一定是向下的。然后就是枚举各种状态了。

由于状态比较多比较复杂可以考虑用dp来表示。

dp[n][now][num][flag]，n表示当前x的位置，now表示当前y的位置，num表示到了当前位置一共有多少个波峰，flag则表示

这个波波动的方向1是向上0表示向下

这样设dp就融阔了所有情况。然后就是状态转移

用一次向上的薄来表示完成了一个波峰。

dp[i][now][num][1] = dp[i-1][pre][num-1][0]+dp[i-1][pre][num][1]（到达i-1的位置时如果这波方向向下那么这次向上的波就增加了一次波峰

所以是从num转移过来。如果这波方向向上那么这次向上的波作用就与上一次冲突所以是从num转移过来）

dp[i][now][num][0] = dp[i-1][pre][num][0]+dp[i-1][pre][num][1]（由于向下的波不决定波峰数于是都是从num转移的）

#include <iostream>#include <cstring>using namespace std;int dp[30][5][20][2];int main() {    int n , t;    cin >> n >> t;    memset(dp , 0 , sizeof(dp));    for(int now = 1 ; now <= 4 ; now++) {        dp[1][now][1][1] = 1;    }    for(int i = 2 ; i <= n ; i++) {        for(int num = 1 ; num <= t ; num++) {            for(int now = 1 ; now <= 4 ; now++) {                for(int pre = 1 ; pre <= 4 ; pre++) {                    if(now > pre) {                        dp[i][now][num][1] += dp[i - 1][pre][num][1] + dp[i - 1][pre][num - 1][0];                    }                    if(now < pre) {                        dp[i][now][num][0] += dp[i - 1][pre][num][1] + dp[i - 1][pre][num][0];                    }                    if(i == 2) {                        dp[i][now][num][0] = 0;                    }                }            }        }    }    int sum = 0;    for(int now = 1 ; now <= 4 ; now++) {        sum += dp[n][now][t][0];    }    cout << sum << endl;    return 0;}

codeforces 14E. Camels（多维dp）