Codeforces Round #277 (Div. 2) LIS of Sequence Dp-白红宇

Codeforces Round #277 (Div. 2) LIS of Sequence Dp

阅读量：4659 次

发布时间：2019-06-09

本文共 1166 字，大约阅读时间需要 3 分钟。

题意：给出一个序列，问每个位置的元素，分别属于哪一类的东西。第一类没有出现在任何的上升子序列中。第三类出现在所有上升子序列中。第二类就是剩下的了。。

求两个东西， dp[i] 表示从1到 i 最长上升子序列的长度，dp1[i]表示从i到n 最长上升子序列的长度。

设原序列最长上升子序列长度为len

1. 若dp[i]+dp1[i] - 1 != len , 他就属于第一类。

2. 若 t = dp[i] 的 t 出现了不止一次，且不属于第一类，那他就是第二类。

剩下的就是第三类了。

代码写的有点戳。

#include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           using namespace std;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1const int maxn = 111111;vector
           
             q[maxn];int erfen(int a[], int l, int r, int key){ int ans = -1; while (l <= r){ int mid = (l + r) >> 1; if (a[mid] >= key){ ans = mid; } if (a[mid] >= key) r = mid - 1; else l = mid + 1; } return ans;}int erfen1(int a[], int l, int r, int key){ int ans = -1; while (l <= r){ int mid = (l + r) >> 1; if (a[mid] <= key){ ans = mid; } if (a[mid] <= key) r = mid - 1; else l = mid + 1; } return ans;}int a[maxn], a1[maxn];int ans[maxn], ans1[maxn];int dp[maxn], dp1[maxn];int vis[maxn];int main(){ int n; memset(vis, 0, sizeof(vis)); int cnt = 0; int cnt1 = 0; scanf("%d", &n); for (int i = 0; i

转载于:https://www.cnblogs.com/yigexigua/p/4097932.html

你可能感兴趣的文章

javascript-装饰者模式

查看>>