题目大意：有一段深搜的代码，是遍历一个邻接矩阵，然后输出一个序列，这个邻接矩阵的原形是一棵树，那么现在就是要你根据序列，求出最多有多少个不同的树遍历之后可以得到相同的序列。
思路：这道题属于简单的区间DP，仔细点想就可以了。
第一种方法也是最直接的思路。
令dp[i][j]表示的是以i这个点为根，其余点为它的子树时，符合条件的最大个数。
从样例可以想到
1 2 3由于3和2交换之后，依然不会影响输出，所以假如1 2 xxx 3xxx，交换2,3节点下的树，也是不会影响序列的。
突破点就在此，dp[i][j]表示的便是一棵以i为根的（子）树，我们要做的就是去比较子树根的大小，判断可以不可以交换。
这边还需明白的一点在于：dp[i][j]表示以i为根的情况，dp[i-1][j]表示的便是i-j中的节点有任意多个节点在同一层的情况。（这个也不知道怎么讲- -！）
第一种方法的状态转移方程：dp[i][j]=dp[i][j]+dp[i+1][k]*dp[k][j](d[k+1]>d[i+1])，这边主要要理解的是不同子树的根能否位于同一层的情况。
AC代码：
#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<cstring>using namespace std;long long dp[505][505];int d[505];#define mod 1000000007;/*dp[i][j]表示i为根时符合条件的情况，最直接的设想。*/int main(){int n;while (cin >> n){for (int i = 1; i <= n; i++)scanf("%d", &d[i]);memset(dp, 0, sizeof(dp));for (int i = 1; i <= n; i++)dp[i][i] = dp[i][i + 1] = 1;for (int len = 2; len < n;len++)for (int i = 1; i + len <= n; i++){int j = i + len;for (int k = i + 1; k <=j;k++)if (k==j||d[k+1]>d[i+1])//k==j是考虑最后一个顶点单独为一个第二层子树的情况{dp[i][j] += dp[i + 1][k] * dp[k][j];dp[i][j] %= mod;}}cout << dp[1][n] << endl;}}
第二种方法：
其实第二种方法跟第一种方法一样，只是表示上没那么直接
dp[i][j]表示的是i-j中的节点有任意多个节点在同一层的情况很明显这边的根便是i-1，并且先输出的是i,
所以最终的结果是dp[2][n+1]
AC代码：
/*dp[i][j] 表示的是i-j当中符合输出序列的树的个数，但需要注意的是这边的i不一定为根，还包括i与i+1-j同一层的情况，，需好好理解。*/int main(){int n;while (cin >> n){for (int i = 1; i <= n; i++)scanf("%d", &d[i]);memset(dp, 0, sizeof(dp));for (int i = 1; i <= n + 1; i++)dp[i][i] = dp[i][i + 1] = 1;for (int len = 2; len <=n;len++)for (int i = 1; i + len <= n+1; i++){int j = i + len;dp[i][j] += dp[i + 1][j];//i单独为节点的情况for (int k = i + 1; k < j;k++)if (d[i] < d[k])//两者的差别在于判断条件。{dp[i][j] += dp[i + 1][k] * dp[k][j];//因为i为节点，所以这个树有dp[i+1][k]种情况dp[i][j] %= mod;}}cout << dp[2][n+1] << endl;}}
问：一只小狗在沙漠中旅行，结果死了，问他是怎么死的？
