起起落落 ccpc wannafly

起起落落 ccpc wannafly

尚未提交 尚未通过 时间限制：1000ms 内存限制：256MB

提交人数：12

通过人数：0

题目描述

无聊的wlswls正在观察某个商品的价格，wlswls一共观察了nn天，每天这个商品都会有一个价格p_ipi​。

定义一个长度为2m+1(3leq2m+1leq n)2m+1(3≤2m+1≤n)的子序列a_{2m+1}a1​...a2m+1​是持续下降的，当且仅当：

1. 1 leq a_1 < a_2 < .... < a_{2m+1} leq n1≤a1​<a2​<....<a2m+1​≤n

2. 对于所有的k(1 leq k leq m)k(1≤k≤m), p_{a[2k - 1]} > p_{a[2k + 1]} > p_{a[2k]}pa[2k−1]​>pa[2k+1]​>pa[2k]​

现在wlswls想知道持续下降的子序列一共有多少个。

由于满足条件的序列可能很多，请输出答案 modmod 1e9+71e9+7。

输入描述

第一行一个整数nn。

接下来一行nn个整数，p_ipi​表示商品第ii天的价格。

1 leq n leq 20001≤n≤2000

1 leq p_i leq n1≤pi​≤n

p_i neq p_jpi​​=pj​

输出描述

一行一个整数表示答案。

样例输入 1 

5
4 2 3 1 5

样例输出 1

1

一开始发现整个合法的子序列是呈一个波浪形下降的趋势，但是不知道有什么用 QAQ
然而就是题解就是从这个趋势下手的。。。。。。。。。
然后就是正的dp，  设dpi为以i为结尾的合法序列有几个，
然后就是这题不能倒着dp   ，   因整体是一个下降的趋势，前面的最低点可能比后面的高点要高。。。。

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int mod = 1e9+7;
 5 long long dp[2010], a[2010];
 6 int main()
 7 {
 8 
 9     //k   2k - 1 2k 2k + 1
10     //1   1      2  3
11     //2   3      4  5
12     //3   5      6  7
13     //4   7      8  9
14 
15     int n;
16     cin >> n;
17     long long ans = 0;
18     for(int i = 0; i < n; ++i) {
19         cin >> a[i];
20     }
21     for(int i = 2; i < n; ++i) {
22         int k = 0;
23         for(int j = i - 1; j >= 0; --j) {
24             if(a[j] < a[i]) {
25                 k++;
26             }else if(a[j] > a[i]){
27                 dp[i] = (dp[i] + (dp[j] + 1) * k) % mod;
28             }
29         }
30         ans = (dp[i] + ans) % mod;
31     }
32     cout << ans << endl;
33     return 0;
34 }

转载于:.html