# 某岛

… : "…アッカリ～ン . .. . " .. .
February 14, 2023

# DP 优化练习

## Luogu P2513. [HAOI2009]逆序对数列

```#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]木棍分割

```#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

```#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);
}
}

```