P1637 三元上升子序列

youyong1 / 2024-10-13 / 原文

dp[i][a[j]]以每一个a[j]为结尾时上升子序列的长度为i：状态转移出来了：if(a[j]>a[k])dp[i][a[j]]+=dp[i-1][a[k]];满足条件则可以转移。可惜时间超限，分析状态的转移过程，到该状态即为前面的所有小于该数的状态得来，考虑用树状数组来维护即可。

点击查看代码

#include <iostream>
#include <stack>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#include <climits>
#include <string.h>
#include <map>
#include <queue>
#include <list>
#include <cmath>
#include <iomanip> 
#define int long long 
#define ios ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lc u<<1
#define rc u<<1|1
#define gcd __gcd
#define double long double
#define endl "\n"
#define INF LLONG_MAX
#define mod  1000000007
#define N 100005
const double PI = 3.14159265358979323846;
using namespace std;
int n, a[N],dp[4][N],b[N];
int lowbit(int x) { return x & (-x); }
void add(int i, int k)
{
    while (i <= 100000)
    {
        b[i] += k;
        i += lowbit(i);
    }
}
int sum(int x)
{
    int ans = 0;
    while (x)
    {
        ans += b[x];
        x -= lowbit(x);
    }
    return ans;
}
signed main()
{
    ios;//会超时
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        dp[1][i] = 1;
    }
    for (int i = 2; i <= 3; i++) 
    {
        for (int j = 1; j <= n; j++)
        {
            int temp = sum(a[j] - 1);
            dp[i][j] += temp;
            add(a[j], dp[i-1][j]);
        }
        for (int j = 1; j <= 100000; j++)b[j] = 0;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)ans += dp[3][i];
    cout << ans << endl;
    return 0;
}