C1641 [Wannafly冬令营2018Day1]起起落落(dp+递推)

C1641 [Wannafly冬令营2018Day1]起起落落(dp+递推)

题目链接：

题目大意是：求下降的波浪线子集个数

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e9 + 7;
typedef long long ll;int n;
ll P[2005], dp[2005];// P[2k - 1] > P[2k + 1] > P[2k]
/*dp[j]表示: 以j结尾的并且满足要求的子序列个数. 那么就有转移: 对于j前面的数字P[i],如果满足P[i] < P[j], 则i可作为目标序列中间点, 而如果碰到P[i] > P[j]的,假设我们已经枚举到了k个可以作为中点的点, 那么当前P[i]可以作为子序列的开始点和这k个中点组合.同时以i结尾的子序列新加上a[j]作为终点也可以和这个k个中点组合. 因此转移方程就是dp[j] += (dp[i] + 1) * k;
*/
int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> P[i];ll ans = 0;for (int i = 3; i <= n; i++){int k = 0;for (int j = i - 1; j >= 1; j--){if(P[j] < P[i])		//向前枚举时, 有可能作为中间点的数目k++;elsedp[i] = (dp[i] + (dp[j] + 1) * k % N) % N;}ans = (ans + dp[i]) % N;}cout << ans << endl;return 0;
}