题面
题目大意:
-
给你一个长度为(n)的序列,元素都在(1-k)之间,有些是(-1),让你把(-1)也变成(1-k)之间的数,使得逆序对最多,求逆序对最少是多少
-
(n<=10000,k<=100)
题解
结论:
填的数是不下降的
证明:
假设相邻的两个-1的位置是(x,y)(a[x]<=a[y]);
如果交换x,y;
对1-x和y-n中的数显然没有影响.
对x-y中大于max(a[x],a[y])和小于min(a[x],a[y])的数显然也没有影响.
但是对x-y中a[x]-a[y]的数,逆序对数显然增加了.
所以交换x,y只会导致逆序对数不降.
所以-1位置的数一定是单调不降的.
(l[i][j])表示前(i)个数有多少大于(j)的数
(r[i][j])表示后(i)个数有多少小于(j)的数
我们把-1位置弄出来(dp)
(f[i][j])表示第(i)位填(j),逆序对个数最少是多少
(b[i])表示第i个空在原序列的位置
假设(i)位填(t)
则
(f[i][t] = min(f[i-1][z]+l[b[i]][t]+r[b[i]][t]))
这样复杂度是(O(n*k^2))
- 注意还要加上没填数时的逆序对
可以发现(f[i-1][z]) 可以用一个前缀最小来优化
Code
#include<bits/stdc++.h>
#define LL long long
#define RG register
using namespace std;
template<class T> inline void read(T &x) {
x = 0; RG char c = getchar(); bool f = 0;
while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;
while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();
x = f ? -x : x;
return ;
}
template<class T> inline void write(T x) {
if (!x) {putchar(48);return ;}
if (x < 0) x = -x, putchar('-');
int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;
for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;
}
const int N= 10010;
int cnt, l[N][110], r[N][110], a[N], b[N];
LL f[N][110], g[N][110];
int main() {
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
int n, k; read(n); read(k);
for (int i = 1; i <= n; i++) {
read(a[i]);
if (a[i] == -1) b[++cnt] = i;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= k; j++) {
l[i][j] = l[i-1][j];
if (a[i] > j) l[i][j]++;
}
for (int i = n; i >= 1; i--)
for (int j = 1; j <= k; j++) {
r[i][j] = r[i+1][j];
if (a[i] < j && a[i] != -1) r[i][j]++;
}
for (int i = 1; i <= cnt; i++) g[i][0] = 1ll << 60;
for (int i = 1; i <= cnt; i++)
for (int j = 1; j <= k; j++) {
f[i][j] = g[i-1][j]+l[b[i]][j]+r[b[i]][j];
g[i][j] = min(g[i][j-1], f[i][j]);
}
LL ans = 1ll << 60;
for (int i = 1; i <= k; i++) ans = min(ans, f[cnt][i]);
for (int i = 1; i <= n; i++) ans += l[i][a[i]];
printf("%lld
", ans);
return 0;
}