BZOJ 5125: [Lydsy1712月赛]小Q的书架

$f[i][k]$ 表示前 $i$ 个分成 $k$ 段,且最后一段以 $i$ 结尾的最小值

容易写出转移方程 $f[i][k] = \min \{f[j][k - 1] + calc(j+1,i)\}$

因为具有决策单调性(打表 or 证明(不会)),就可以一种分治算法来优化

具体实现就是 $solve(l,r,L,R)$ 表示要求出 $(l,r)$ 之间的 dp 值,而决策点能取的区间为 $[L,R]$

先暴力求出 $mid=\dfrac{l+r}{2}$ 的决策点 $pos$,再调用 $solve(l,mid-1,L,pos)$,$solve(mid+1,r,pos,R)$ 即可。

$calc(i,j)$ 就是求区间逆序对,用莫队,拓展时用树状数组即可。

![]()![]()```

include <bits/stdc++.h>

define ll long long

const int N = 4e4 + 7;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll dp[2][N], sum;
int cnt[N], n, k, l = 1, r, cur, last, a[N];

struct Bit {
int tree[N];
inline int lowbit(int x) {
return x & -x;
}
void add(int x, int v) {
if (x <= 0) return;
for (int i = x; i <= n; i += lowbit(i))
tree[i] += v;
}
int query(int x) {
if (x <= 0) return 0;
int ans = 0;
for (int i = x; i; i -= lowbit(i))
ans += tree[i];
return ans;
}
} bit;

void calc(int x, int y) {
while (l < x) {
sum -= bit.query(a[l] - 1);
bit.add(a[l++], -1);
}
while (l > x) {
l--;
sum += bit.query(a[l] - 1);
bit.add(a[l], 1);
}
while (r > y) {
sum -= bit.query(n) - bit.query(a[r]);
bit.add(a[r--], -1);
}
while (r < y) {
++r;
sum += bit.query(n) - bit.query(a[r]);
bit.add(a[r], 1);
}
}

void solve(int l, int r, int L, int R) {
if (l > r) return;
int mid = l + r >> 1;
dp[cur][mid] = inf;
int pos = 0;
for (int i = L; i <= std::min(mid, R); i++) {
calc(i, mid);
if (dp[cur][mid] > dp[last][i - 1] + sum)
dp[cur][mid] = dp[last][i - 1] + sum, pos = i;
}
solve(l, mid - 1, L, pos); solve(mid + 1, r, pos, R);
}

int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d", a + i);
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
last = 0; cur = 1;
while (k--) {
solve(1, n, 1, n);
std::swap(cur, last);
}
printf("%lld\n", dp[last][n]);
return 0;
}



View Code

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。