5 4
4 2 -1 -1 3
tro for family bzoj pac return border [0
题解:结论!!!为了使逆序对最少,我们在 - 1 位置填入的数一定是单调不减的。(可以用反证法证明,很简单。)
所以 DP,我们用 f[i][j] 表示枚举到第 i 个数,上一个在 - 1 位置填入的数是 j 个最少逆序对个数。然后转移也很简单~
- #include < cstdio > #include < cstring > #include < iostream > using namespace std;
- const int maxn = 10010;
- int n,
- k,
- tot,
- ans,
- sum;
- int f[110][maxn],
- s[110],
- sv[110],
- cnt,
- sm,
- v[maxn];
- int main() {
- memset(f, 0x3f, sizeof(f));
- int i,
- j;
- scanf("%d%d", &n, &k);
- for (i = 1; i <= n; i++) {
- scanf("%d", &v[i]);
- if (v[i] != -1) {
- sum += tot - sv[v[i]],
- tot++;
- for (j = v[i]; j <= k; j++) sv[j]++;
- }
- }
- for (i = 1; i <= k; i++) f[i][0] = 0;
- for (i = 1; i <= n; i++) {
- if (v[i] != -1) {
- cnt++;
- for (j = 1; j <= k; j++) f[j][i] = f[j][i - 1];
- for (j = v[i]; j <= k; j++) s[j]++;
- continue;
- }
- for (sm = 1 << 30, j = 1; j <= k; j++) {
- sm = min(sm, f[j][i - 1]);
- f[j][i] = sm + cnt - s[j] + (sv[j - 1] - s[j - 1]);
- }
- }
- ans = 1 << 30;
- for (i = 1; i <= k; i++) ans = min(ans, f[i][n]);
- printf("%d", ans + sum);
- return 0;
- }
【BZOJ1786】[Ahoi2008]Pair 配对 DP
来源: http://www.bubuko.com/infodetail-2158346.html