• https://www.cnblogs.com/flashhu/p/9480669.html

Luogu P2513. [HAOI2009]逆序对数列

• https://www.luogu.com.cn/problem/P2513

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e3) + 9;
int f[N];
int n, m;

int main(){

#ifndef ONLINE_JUDGE
     //freopen("in.txt", "r", stdin);
#endif

    RD(n, m); f[0] = 1;
    FOR(i, 1, n) {
        DWN_1(j, m, 1) {
            int t = max(0, j-i);
            DWN(k, j, t) f[j] += f[k];
            f[j] %= 10000;
        }
    }
    cout << f[m] << endl;
}

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e3) + 9;
int f[N], s[N];
int n, m;

int main(){

#ifndef ONLINE_JUDGE
     //freopen("in.txt", "r", stdin);
#endif

    RD(n, m); f[0] = 1;
    FOR(i, 1, n) {
        REP(j, m) s[j+1] = s[j] + f[j];
        DWN_1(j, m, 1) {
            f[j] += s[j] - s[max(0, j-i)];
            f[j] %= 10000;
        }
    }
    cout << f[m] << endl;
}

Luogu P2511. [HAOI2008]木棍分割

• https://www.luogu.com.cn/problem/P2511

这个暴力反而不太好写。。。对于每个状态，大概需要分别有 best[i][j], ways[i][j] 表示长度为 j 恰好切 i 段，时的最优解和方案数。
但转移的方程里面有 max() 导致非常难以优化。

进一步我们发现 best 是可以直接二分出来的。。。有了最大切痕长度，在考虑 dp 方案数就简化非常多了。。（此时我们在最后的最大切痕一定等于 best。。即使中间允许不满足）

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(5e4) + 9;
int a[N], s[N], lt[N]; int ways[N], sums[N];
int n, m, p, q;

bool ok(int x) {
    int cur = 0, cnt = 0;
    REP_1(i, n) {
        if (cur + a[i] > x) cur = 0, ++cnt;
        cur += a[i];
    }
    return cnt <= m;
}

int get_cut() {
    int l = *max_element(a+1, a+n+1), r = s[n];
    while (l < r) {
        int m = (l + r) / 2;
        if (ok(m)) r = m;
        else l = m + 1;
    }
    return l;
}

int main() {

#ifndef ONLINE_JUDGE
     freopen("in.txt", "r", stdin);
#endif

    MOD = 10007;
    RD(n, m); REP_1(i, n) s[i] = s[i-1] + RD(a[i]);
    int cut = get_cut();

    int l = 0; REP_1(i, n) {
        while (s[i] - s[l] > cut) ++l;
        lt[i] = l;
    }

    REP_1(i, n) if (s[i] <= cut) ways[i] = 1; else break;
    int tot = ways[n];

    REP_1(i, m) {
        REP(j, n) sums[j+1] = sums[j] + ways[j];
        REP_1(j, n) {
            ways[j] = (sums[j] - sums[lt[j]]) % MOD;
            if (ways[j] < 0) ways[j] += MOD;
        }
        tot += ways[n];
    }
    tot %= MOD;
    printf("%d %d\n", cut, int(tot));
}

P3515 [POI2011]Lightning Conductor

• https://www.luogu.com.cn/problem/P3515

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(5e5) + 9;
int a[N];
int n;


int main() {

#ifndef ONLINE_JUDGE
     freopen("in.txt", "r", stdin);
#endif

    RD(n); REP(i, n) RD(a[i]);

    REP(i, n) {
        int z = 0;

        REP(j, n) {
            int t = sqrt(abs(i-j)); if (t*t < abs(i-j)) ++t;
            checkMax(z, (a[j] - a[i]) + t);
        }
        printf("%d\n", z);
    }
}