CSP第22次 202104-4 校门外的树 C语言答案

先讲一下思路：

数组 arr[i] 记录每个障碍物的位置，arr[1] 即第一个障碍物的位置
数组 dp[i][j] 记录第 i 个障碍物到第 j 个障碍物的方案数(内部不组合！！！)
数组 count[i] 记录前 i 个障碍物总的方案数

那么count[i]可以这么求
count[1] = 1
count[2] = dp[1][2]
count[3] = dp[1][3]     +dp[1][2]*dp[2][3]
count[4] = dp[1][4]     +dp[1][2]*dp[2][4] +dp[1][3]*dp[3][4]     +dp[1][2]*dp[2][3]*dp[3][4]
count[5] = dp[1][5]     +dp[1][2]*dp[2][5] +dp[1][3]*dp[3][5] +dp[1][4]*dp[4][5]     +dp[1][2]*dp[2][3]*dp[3][5] +dp[1][2]*dp[2][4]*dp[4][5] +dp[1][3]*dp[3][4]*dp[4][5]     +dp[1][2]*dp[2][3]*dp[3][4]*dp[4][5]

仅仅调整一下相加的顺序，方便大家观察
count[1] = 1
count[2] = dp[1][2]
count[3] = dp[1][3]     +dp[1][2]*dp[2][3]
count[4] = dp[1][4]     +dp[1][2]*dp[2][4]     +dp[1][3]*dp[3][4] +dp[1][2]*dp[2][3]*dp[3][4]
count[5] = dp[1][5]     +dp[1][2]*dp[2][5]     +dp[1][3]*dp[3][5] +dp[1][2]*dp[2][3]*dp[3][5]     +dp[1][4]*dp[4][5] +dp[1][2]*dp[2][4]*dp[4][5] +dp[1][3]*dp[3][4]*dp[4][5] +dp[1][2]*dp[2][3]*dp[3][4]*dp[4][5]

将dp[][]尽可能地替换成count后
count[1] = 1
count[2] = count[1]*dp[1][2]
count[3] = count[1]*dp[1][3]     +count[2]*dp[2][3]
count[4] = count[1]*dp[1][4]     +count[2]*dp[2][4]     +count[3]*dp[3][4]
count[5] = count[1]*dp[1][5]     +count[2]*dp[2][5]     +count[3]*dp[3][5]     +count[4]*dp[4][5]

以上就是本题动态规划的状态转移公式了
是不是很神奇！我研究了好长时间才想清楚，所以为了方便各位理解我这里详细地把式子的变化过程都敲出来了，点个赞就当劳动费吧哈哈

//纯C语言60分代码
#include 

int arr[1010];//记录每个障碍物的坐标
int obstacle[100010]={0};//标记哪些点是障碍物
long long dp[1010][1010];//第 a 个障碍物到第 b 个障碍物的方案数(内部不组合！！！)
long long ans[1010]={0};//前 i 个障碍物总的方案数
const int mod = 1e9 + 7;

int computeDp(int a,int b)//求第 a 个障碍物到第 b 个障碍物的方案数(内部不组合！！！)
{
    int i,j,difference=arr[b]-arr[a],count=0;
    for(i=1;i