Description
Mary在她的生日禮物中有一些積木。那些積木都是相同大小的立方體。每個積木上面都有一個數(shù)。Mary用他的 所有積木壘了一個高塔。媽媽告訴Mary游戲的目的是建一個塔，使得最多的積木在正確的位置。一個上面寫有數(shù)i 的積木的正確位置是這個塔從下往上數(shù)第i個位置。Mary決定從現(xiàn)有的高塔中移走一些，使得有最多的積木在正確 的位置。請你告訴Mary她應(yīng)該移走哪些積木。 Input
第一行為一個數(shù)n，表示高塔的初始高度。第二行包含n個數(shù)a1,a2,…,an，表示從下到上每個積木上面的數(shù)。 (1<=n<=100000,1<=ai<=1000000)。 Output
注意：請輸出最多有多少點(diǎn)可以處在正確位置 Sample Input 5
1 1 2 5 4 Sample Output 3
解題方法： 我們先列一下普通的DP方程，
然后這里就是3個限制條件了？CDQ三維偏序？翻了翻題解，發(fā)現(xiàn)神思路的題目。觀察三個限定條件。
容易發(fā)現(xiàn)已知2,3可以推出1。 而1代表的是這n個數(shù)的排列順序。 而2的條件即為最長上升子序列。 所以我們不妨把3看做這n個數(shù)的重新排列法則，之后滿足2的條件即可。 所以我們只需要按照j?a[j]<=i?a[i]把n個數(shù)重新排列，接著求一個最長上升子序列長度即可。 需要注意的是，如果i?a[i]<0的話，那么顯然這個數(shù)不可能與C序列中的某個數(shù)對應(yīng)上，直接跳過即可。
LIS可以二分也可以用樹狀數(shù)組的方法，PO爺用的樹狀數(shù)組的方法，可以看PO爺博客，蒟蒻寫了一個代碼和博主幾乎一樣的二分版本的代碼。
#include <bits/stdc++.h>using namespace std;const int maxn = 100010;const int maxm = 1000010;struct node{ int x, y; node(){} node(int x, int y) : x(x), y(y) {} bool Operator < (const node &rhs) const{ if(x == rhs.x) return y < rhs.y; return x < rhs.x; }}b[maxn];int n, cnt, ans, d[maxm], a[maxn];int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); if(i - a[i] < 0) continue; b[++cnt].x = i - a[i], b[cnt].y = a[i]; } sort(b + 1, b + cnt + 1); memset(d, 0x3f, sizeof(d)); for(int i = 1; i <= cnt; i++) { int l = 1, r = ans, len = 0; while(l <= r){ int mid = (l + r) / 2; if(b[i].y > d[mid]){ len = mid, l = mid + 1; } else{ r = mid - 1; } } ans = max(ans, len + 1); d[len + 1] = min(d[len + 1], b[i].y); } cout << ans << endl; return 0;}新聞熱點(diǎn)
疑難解答
