[BZOJ1786][BZOJ1831]逆序对

试题描述

输入

输出

输入示例

- -

输出示例

数据规模及约定

见“输入”

题解

首先这题有一个性质，即，填的数从左到右一定不降。证明不妨读者自己yy（提示：用先按降序填，交换后答案一定不会更差的思想证）。

那么新添的数字一定不会造出逆序对了。

然后设计 dp，设 f(i, j) 表示考虑前 i 个打“-1”的位置，最后一个（第 i 个）位置填写数字 j 时，与已经固定的数字产生最少的逆序对数。

有 f(i, j) = min{ f(i-1, x) | 0 < x ≤ j } + lager(pos[i], j) + smaller(pos[i], j)，其中，pos[i] 表示第 i 个“-1”在原数列中的位置，larger(i, j) 表示第 1~i-1 个已知数中比 j 大的数的个数，smaller(i, j) 表示第 i+1~n 个已知数中比 j 小的数的个数。

答案是 min{ f(cnt, x) | 0 < x ≤ k } + ans，其中 cnt 表示 -1 的个数，ans 表示已知数字中逆序对个数。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <stack>

#include <vector>

#include <queue>

#include <cstdlib>

using namespace std;

const int BufferSize = 1 << 16;

char buffer[BufferSize], *Head, *tail;

inline char Getchar() {

    if(Head == tail) {

        int l = fread(buffer, 1, BufferSize, stdin);

        tail = (Head = buffer) + l;

    }

    return *Head++;

}

int read() {

	int x = 0, f = 1; char c = Getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }

	return x * f;

}

#define maxn 10010

#define maxk 110

#define oo 2147483647

int n, k, A[maxn], f[maxn][maxk], la[maxn][maxk], sm[maxn][maxk], pos[maxn], cnt;

int c[maxn];

void add(int x) { for(; x <= k; x += x & -x) c[x]++; return ; }

int sum(int x) { int res = 0; for(; x; x -= x & -x) res += c[x]; return res; }

int main() {

	n = read(); k = read();

	for(int i = 1; i <= n; i++) A[i] = read();

	int ans = 0;

	for(int i = n; i; i--) {

		if(A[i] >= 0) add(A[i]), ans += sum(A[i] - 1);

		for(int j = 2; j <= k; j++) sm[i][j] = sum(j - 1);

	}

	memset(c, 0, sizeof(c));

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

		if(A[i] >= 0) add(k - A[i] + 1);

		else pos[++cnt] = i;

		for(int j = 1; j < k; j++) la[i][j] = sum(k - j);

	}

	for(int i = 1; i <= k; i++) f[0][i] = 0;

	for(int i = 1; i <= cnt; i++)

		for(int j = 1; j <= k; j++) {

			f[i][j] = oo;

			for(int x = 1; x <= j; x++) f[i][j] = min(f[i][j], f[i-1][x]);

			f[i][j] += la[pos[i]][j] + sm[pos[i]][j];

		}

	int sum = oo;

	for(int i = 1; i <= k; i++) sum = min(sum, f[cnt][i]);

	printf("%d\n", ans + sum);

	return 0;

}

秒客网

[BZOJ1786][BZOJ1831]逆序对

相关文章