題目鏈接：
http://acm.hust.edu.cn/vjudge/contest/127406#problem/E
Description
http://7xjob4.com1.z0.glb.clouddn.com/0f10204481da21e62f8c145939e5828e
Input
The input file contains several test cases, each of them as described below.
The first line has one integer N and the second line contains a permutation of the integers from 1
to N + 1. Integers in the same line are separated by a single space.
Constraints:
1 ≤ N < 2000 Number of Arrows.
Output
For each test case, the output has a single line with the number (modulo 2
31 ? 1 = 2147483647) of
distinct signs that can be described by the given permutation.
Sample Input
5
2 6 5 1 4 3
2
2 3 1
20
3 21 10 15 6 9 2 5 20 13 17 19 14 7 11 18 16 12 1 8 4
Sample Output
6
1
1887
題意：
木匠要做N個路標并把它們釘在一起(如圖).
每個路標可以朝左也可以朝右，但是每個路標的起點要跟下一層路標的起點或終點重合. 重合位置必須有面積覆蓋，不能像231右圖那種只重合一個點.
現在他不記得這些路標各自的朝向了. 但是他記得N+1個值，其中第i個值是第i個路標的起點坐標. (第N+1為最后一塊的終點).
求可能滿足條件的路標有多少種情況. (區別在于各自的朝向)(第一塊路標一定朝右)
題解：
考慮每塊路標的終點：
若第i塊路標的坐標區間為[L, R], 第i+1塊路標的終點為Xi+1.
那么基于第i塊路標來擺放第i+1塊的方式有兩種：
①第i+1塊的起點在L處(朝右). 這要求 Xi+1 > L .
②第i+1塊的起點在R處(朝左). 這要求 Xi+1 < R .
基于以上遞歸關系來進行動態規劃：
dp[i][0][j]: 表示第i塊板子的區間為 [j, Xi] 的方案數(朝右).
dp[i][1][j]: 表示第i塊板子的區間為 [Xi, j] 的方案數(朝左).
再根據"我為人人"的思想從第 i 塊拓展到第 i+1 塊即可.
代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <list>
#define LL long long
#define eps 1e-8
#define maxn 2016
#define mod 2147483647LL
#define inf 0x3f3f3f3f
#define mid(a,b) ((a+b)>>1)
#define IN freopen("in.txt","r",stdin);
using namespace std;LL dp[maxn][2][maxn];
int n, arrow[maxn];int main(int argc, char const *argv[])
{//IN;while(scanf("%d", &n) != EOF){int leftmost; scanf("%d", &leftmost);for(int i=1; i<=n; i++)scanf("%d", &arrow[i]);memset(dp, 0, sizeof(dp));dp[1][0][leftmost] = 1;for(int i=1; i<n; i++) {for(int j=1; j<=n+1; j++) {if(dp[i][0][j]) {if(arrow[i+1] > j) dp[i+1][0][j] = (dp[i+1][0][j] + dp[i][0][j]) % mod;if(arrow[i+1] < arrow[i]) dp[i+1][1][arrow[i]] = (dp[i+1][1][arrow[i]] + dp[i][0][j]) % mod;}if(dp[i][1][j]) {if(arrow[i+1] < j) dp[i+1][1][j] = (dp[i+1][1][j] + dp[i][1][j]) % mod;if(arrow[i+1] > arrow[i]) dp[i+1][0][arrow[i]] = (dp[i+1][0][arrow[i]] + dp[i][1][j]) % mod;}}}LL ans = 0;for(int j=1; j<=n+1; j++) {ans = (ans + dp[n][0][j]) % mod;ans = (ans + dp[n][1][j]) % mod;}printf("%lld\n", ans);}return 0;
}
