bzoj 1109

사고방식: 우리가 dp[i]를 고려하면 i가 지정한 위치에서 가장 큰 개수를 나타낸다.
dp[ i ] = max(dp[ j ] + 1)  
j는 3가지 조건을 충족시켜야 한다
1. j < i
2. a[ j ] < a[ i ]
3. a[ i ] - a[ j ] <= i - j
2, 3을 통해서 저희가 1을 내놓을 수 있어요.
그래서 사실 2차원 편차 문제예요.
a[i]로 정렬한 후 트리 배열로 해결하거나 LIS 문제로 전환할 수 있습니다.

#include
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair

using namespace std;

const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 +7;

int a[N], n;

pii p[N];
void modify(int x, int v) {
    for(int i = x; i < N; i += i & -i) {
        a[i] = max(a[i], v);
    }
}

int getMx(int x) {
    int ans = 0;
    for(int i = x; i; i -= i & -i) {
        ans = max(ans, a[i]);
    }
    return ans;
}

bool cmp(pii a, pii b) {
    if(a.fi == b.fi) return a.se - a.fi > b.se - b.fi;
    return a.fi < b.fi;
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &p[i].fi);
        p[i].se = i;
    }

    sort(p + 1, p + 1 + n, cmp);

    int ans = 0;

    for(int i = 1; i <= n; i++) {
        if(p[i].se - p[i].fi < 0)
            continue;

        int mx = getMx(p[i].se - p[i].fi + 1);
        modify(p[i].se - p[i].fi + 1, mx + 1);
        ans = max(ans, mx + 1);

    }

    printf("%d
", ans);
    return 0;
}
/*
*/

 
전재 대상:https://www.cnblogs.com/CJLHY/p/9192956.html