【题目描述】
小可可和小卡卡想到Y岛上旅游，但是他们不知道Y岛有多远。好在，他们找到一本古老的书，上面是这样说的： 下面是$N$个正整数，每个都在$1\sim K$之间。如果有两个数$A$和$B$，$A$在$B$左边且$A$大于$B$，我们就称这两个数为一个“逆序对”。你数一数下面的数字里有多少个逆序对，你就知道Y岛离这里的距离是多少千米了。 比如说，$4,2,1,3,3$里面包含了$5$个逆序对：$(4, 2), (4, 1), (4, 3), (4, 3), (2, 1)$。 可惜的是，由于年代久远，这些数字里有一部分已经模糊不清了，为了方便记录，小可可用$-1$表示它们。比如说，$4,2,-1,-1,3$可能原来是$4,2,1,3,3$，也可能是$4,2,4,4,3$，也可能是别的样子。小可可希望知道，根据他们看清楚的这部分数字，能不能推断出这些数字里最少能有多少个逆序对。
【输入格式】
第一行两个正整数$N$和$K$。第二行$N$个整数，每个都是$-1$或是一个在$1\sim K$之间的数。
$N\le 10000, K\le 100$
【输出格式】
一个正整数，即这些数字里最少的逆序对个数。
###题解
首先证明一下$-1$的地方填的数一定是单调不降的
假设$A\le B$那么现在的逆序对数是$a+b+y$如果交换$a,b$那么逆序对数会变成$a+b+x$或者$a+b+x+1$(取决于$A=B$)
由于$A\le B$所以$y\le x$所以$a+b+y\le a+b+x<a+b+x+1$在$A,B$右边小于$A,B$的也同理 不证了 所以肯定是不交换，即$A\le B$比较优
我们完全可以先把那些不是$-1$的元素之间的逆序对先算出来 然后我们就只用计算每个$-1$位置产生的逆序对数了
预处理出$sumfr[i][j]$表示$a[1\sim i]$除$-1$外有多少个大于$j$的数，$sumbk[i][j]$表示$a[i\sim n]$除$-1$外有多少个小于$j$的数
子状态：$dp[i][j]$表示前$i$个$-1$最后一个填了$j$的最小逆序对数$pos[i]$表示第$i$个$-1$在原数组中的下标
由于我们刚才推出了那个单调不降的性质 转移方程就很简单了：$dp[i][j]=\min\limits_{k=1}^{j}dp[i-1][k]+sumfr[pos[i]-1][j]+sumbk[pos[i]+1][j]$
时间复杂度$O(nk)$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define N 20005
#define K 205
using namespace std;
typedef long long ll;
inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
return x * f;
}
int n, m, a[N];
ll sumfr[N][K], sumbk[N][K];
ll dp[N][K];
ll tr[N], ans;
int q[N], tot;
inline void update(int ind, int v) {
for (; ind <= m; ind += lowbit(ind)) {
tr[ind] += v;
}
}
inline ll getsum(int ind) {
ll ret = 0;
for (; ind; ind -= lowbit(ind)) {
ret += tr[ind];
}
return ret;
}
inline void getans() {
ans = 0;
memset(tr, 0, sizeof(tr));
for (int i = 1; i <= n; i++) {
if (a[i] == -1) continue;
ans += getsum(m) - getsum(a[i]);
update(a[i], 1);
}
}
inline void init() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sumfr[i][j] = sumfr[i-1][j];
if (a[i] != -1) sumfr[i][j] += (a[i] > j);
}
}
for (int i = n; i; i--) {
for (int j = 1; j <= m; j++) {
sumbk[i][j] = sumbk[i+1][j];
if (a[i] != -1) sumbk[i][j] += (a[i] < j);
}
}
for (int i = 1; i <= n; i++) {
if (a[i] == -1) {
q[++tot] = i;
}
}
}
int main() {
n = read(); m = read();
for (int i = 1; i <= n; i++) a[i] = read();
getans();
init();
memset(dp, 0x3f, sizeof(dp));
for (int j = 1; j <= m; j++) dp[0][j] = 0;
for (int i = 1; i <= tot; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = min(dp[i][j-1], dp[i-1][j]);
}
for (int j = 1; j <= m; j++) {
dp[i][j] += sumfr[q[i]-1][j] + sumbk[q[i]+1][j];
}
}
ll mn = 0x3f3f3f3f3f3f3f3f;
for (int j = 1; j <= m; j++) {
mn = min(mn, dp[tot][j]);
}
printf("%lld\n", ans + mn);
return 0;
}
|
