[luogu] P1108 低价购买 最长上升子序列

前言

我也太菜了吧,这都没想到 传送门 : https://www.luogu.com.cn/problem/P1108

思路

O n^3的做法 一定是不行的

所以我们需要考虑 O n^2的做法 或者是 更低

因为我们需要统计答案的种类数 所以不难想象我们还需要在 转移的时候 再加一个dp

这样子我们才能记录

因此我们需要在每次需要做转移的时候 都要记录一个 t[ i ] 表示 当前是由 几个数转移过来的

因此 思路就清晰起来了

CODE

#include 
#define int long long
using namespace std;
const int N = 5e5+10;
using ll = long long;
int f[N],a[N];
int t[N];

void solve()
{
    int n;
    cin>>n;

    for(int i=1; i>a[i];
        f[i] =1 ;
     }

     int maxx = 0 ;
     for(int i=1;i