首页 > 代码库 > Codeforces Round #277 (Div. 2) LIS of Sequence Dp
Codeforces Round #277 (Div. 2) LIS of Sequence Dp
题意： 给出一个序列，问每个位置的元素，分别属于哪一类的东西。第一类 没有出现在任何的上升子序列中。 第三类 出现在所有上升子序列中 。第二类 就是剩下的了。。
求两个东西 ， dp[i] 表示 从1到 i 最长上升子序列的长度，dp1[i]表示从i到n 最长上升子序列的长度。
设原序列最长上升子序列长度为len
1. 若dp[i]+dp1[i] - 1 != len , 他就属于第一类。
2. 若 t = dp[i] 的 t 出现了不止一次，且不属于第一类，那他就是第二类。
剩下的就是第三类了。
代码写的有点戳。
#include<iostream>#include<cstdio>#include<cstring>#include<map>#include<vector>#include<stdlib.h>using namespace std;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1const int maxn = 111111;vector<int> 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<n; i++) scanf("%d", &a[i]); ans[cnt++] = a[0]; dp[0] = 1; for (int i = 1; i<n; i++){ int t = erfen(ans, 0, cnt - 1, a[i]); if (t == -1){ ans[cnt++] = a[i]; dp[i] = cnt; } else{ ans[t] = a[i]; dp[i] = t + 1; } } for (int i = 0; i<n; i++){ a1[i] = a[n - i - 1]; } cnt1 = 0; ans1[cnt1++] = a1[0]; dp1[0] = 1; for (int i = 1; i<n; i++){ int t = erfen1(ans1, 0, cnt1 - 1, a1[i]); if (t == -1){ ans1[cnt1++] = a1[i]; dp1[i] = cnt1; } else{ ans1[t] = a1[i]; dp1[i] = t + 1; } } for (int i = 0; i<n / 2; i++) swap(dp1[i], dp1[n - i - 1]); for (int i = 0; i<n; i++){ int t = dp[i] + dp1[i] - 1; if (t != cnt) vis[i] = 1; } for (int i = 0; i<n; i++){ if (vis[i]) continue; q[dp[i]].push_back(i); } for (int i = 0; i<n; i++){ int len = q[i].size(); if (len <= 1) continue; for (int j = 0; j<len; j++){ int t = q[i][j]; vis[t] = 2; } } for (int i = 0; i<n; i++){ if (!vis[i]) printf("3"); else printf("%d", vis[i]); } cout << endl; return 0;}
Codeforces Round #277 (Div. 2) LIS of Sequence Dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。