제목 링크: hdu 4719 Oh My Holy FFF

제목의 대의: 대열에 n명이 있는데 모든 사람의 키를 주고 그들은 순서대로 배열한다. 지금 이 n명을 몇 조로 나누어야 한다. 각 조의 인원은 l보다 크면 안 된다. 그리고 i조의 마지막 사람의 키는 반드시 i-1조의 마지막 사람의 키보다 크다.마지막 값이 가장 크도록 요구합니다. 값 계산 방법은 제목에서 k가 그룹 번호입니다.
문제풀이 사고방식: dp[i]는 제i개인을 끝으로 하는 최대 권한을 나타낸다. 그러면 dp[i]는 앞의 l-1에서 옮겨온 것이 틀림없다. 즉, dp[i]=dp[j]+h[i]2-h[j]는 h[i]>h[j]를 요구한다.그러나 이러한 복잡도는 o(n2)이고 n은 최대 105이다. 시간적으로 받아들일 수 없기 때문에 라인 트리로 조회 조작을 대체한다. 그러나 이동하는 조건은 h[i]>h[j]라고 한다. 그래서 우리는 먼저 모든 사람을 키에 따라 순서를 정해야 한다. 그러면 하나하나 계산하면 키의 제한을 고려할 필요가 없다. 왜냐하면 이미 업데이트된 값이 있으면 키는 현재 고려해야 할 사람보다 작을 것이다.그리고 찾을 값 b[i]=dp[i]--h[j].세그먼트 트리가 정식으로 접촉한 적이 없기 때문에 매우 비벼서 썼고 갱신도 지연되지 않았다.

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;
typedef long long ll;
const int N = 1e5+5;

struct state {
    int pos;
    ll high;
}p[N];

struct node {
    int left;
    int right;
    ll val;
}t[N*4];

int n, k;
ll dp[N];

inline ll max(ll a, ll b) {
    return a > b ? a : b;
}

ll BuildTree (int c, int l, int r) {
    t[c].left = l;
    t[c].right = r;

    if (l == r) {
        t[c].val = -1;
    } else {
        int mid = (l + r)/2;
        t[c].val = max(BuildTree(c*2, l, mid), BuildTree(c*2+1, mid+1, r));
    }

    return t[c].val;
}

ll Query (int c, int l, int r) {
    if (l == t[c].left && r == t[c].right)
        return t[c].val;

    int mid = (t[c].left + t[c].right) / 2;
    if (l <= mid && r > mid)
        return max(Query(c*2, l, mid), Query(c*2+1, mid+1, r));
    else if (l <= mid && r <= mid)
        return Query(c*2, l, r);
    else
        return Query(c*2+1, l, r);
}

ll upDate (int c, int l, int r, ll val) {
    if (l == t[c].left && r == t[c].right) {
        t[c].val = val;
        return val;
    }

    int mid = (t[c].left + t[c].right) / 2;
    if (l <= mid && r > mid)
        return t[c].val = max(upDate(c*2, l, mid, val), upDate(c*2+1, mid+1, r, val));
    else if (l <= mid && r <= mid)
        return t[c].val = max(upDate(c*2, l, r, val), t[c*2+1].val);
    else
        return t[c].val = max(t[c*2].val, upDate(c*2+1, l, r, val));
}

inline bool cmp (const state& a, const state& b) {
    if (a.high != b.high)
        return a.high < b.high;
    return a.pos > b.pos;
}

void init () {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        cin >> p[i].high;
        p[i].pos = i;
    }
    sort(p+1, p+n+1, cmp);

    BuildTree(1, 0, n);
}

ll solve () {

    upDate(1, 0, 0, 0);
    for (int i = 1; i <= n; i++) {

        dp[p[i].pos] = -1;
        ll val = Query(1, max(0, p[i].pos-k), p[i].pos-1);
        //cout << val << " " << p[i].pos << endl;

        if (val == -1) 
            continue;

        dp[p[i].pos] = val + p[i].high * p[i].high;

        if (p[i].pos == n)
            break;
        upDate(1, p[i].pos, p[i].pos, dp[p[i].pos] - p[i].high);
    }
    return dp[n];
}

int main () {
    int cas;
    scanf("%d", &cas);
    for (int i = 1; i <= cas; i++) {
        init ();
        cout << "Case #" << i << ": ";

        ll ans = solve();
        if (ans <= 0)
            cout << "No solution" << endl;
        else
            cout << ans << endl;
    }
    return 0;
}