【问题描述】

有一个长度为n的序列a1~an,求有多少子序列,满足这个子序列中存在长度为3的上升子序列。

注意,上升是指严格大于,比如1 2 3 可以而1 1 3不行。

由于答案很大,请将答案mod 10009后输出。

【输入格式】

第一行为一个正整数n

接下来一行有n个正整数a[i]

【输出格式】

输出一行,一个整数,为答案。

【输入样例】

4

1 2 3 4

【输出样例】

5

【样例解释】

子序列:1 2 3 、1 2 4、1 3 4、2 3 4 、1 2 3 4均符合条件。

【数据范围】

对于100%的输入数据:n≤100 |a[i]|≤10^4

正向考虑很麻烦,我们可以逆向计算出不符合条件的子序列个数A,然后答案就是2^n-A

对于一个数x,考虑它能够加进前面的序列使得这个序列不含长度为3的上升子序列的条件。

我们可以记录一下从前i个数中选序列,使得最小数为j 次小数为k的方案,设为dp[i][j][k]。

其中j=0表示空集,k=0表示子序列不含长度为2的子序列。

令x=a[i+1]

首先考虑不选入x的情况 那么dp[i+1][j][k]+=dp[i][j][k]

选入x的情况:

①j=0&&k=0 此时直接选入x ,即dp[i+1][x][0]+=dp[i][0][0];

②j!=0&&k==0

I x>j将x选为次小:dp[i+1][j][x]+=dp[i][j][0]

否则II x<=j将j替换为x:dp[i+1][x][0]+=dp[i][j][0]

③j!=0&&k!=0

I x<=j 将j替换为x: dp[i+1][x][k]+=dp[i][j][k]

否则II x≤k 将k替换为x:dp[i+1][j][x]+=dp[i][j][k]

最后减掉dp[n][i][j]即可。

离散化之类的就不用说了吧。

下面是代码:

 

 

本文为原创文章,唯一地址链接:【Sequence】 转载请注明转自 stdKonjac

我来吐槽

*

*

取消

*