BZOJ 1831: [AHOI2008]逆序对

题目大意：

给出一个序列，有几个位置上的数字任意。求最小的逆序对数。

题解：

自己决定放置的数一定是单调不降的。不然把任意两个交换一下就能证明一定会增加逆序对。

然后就可以DP了，f[i][j]表示第i个位置放了j，前i个位置所能产生的最少逆序对数。

用前缀min优化一下就好了。

代码：

#include<cstdio>

#include<algorithm>

using namespace std;

int cnt,suml[10005][105],sumr[10005][105],a[10005],b[10005];

long long f[10005][105],g[10005][105];

int main(){

	int n,k;

	scanf("%d%d",&n,&k);

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

		scanf("%d",&a[i]);

		if (a[i]==-1) b[++cnt]=i;

	}

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

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

			suml[i][j]=suml[i-1][j];

			if (a[i]>j) suml[i][j]++;

 		}

 	for (int i=n; i>=1; i--)

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

			sumr[i][j]=sumr[i+1][j];

			if (a[i]<j && a[i]!=-1) sumr[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]+suml[b[i]][j]+sumr[b[i]][j];

			g[i][j]=min(g[i][j-1],f[i][j]);

		}

	long long ans=1ll<<60;

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

	for (int i=1; i<=n; i++) ans+=suml[i][a[i]];

	printf("%lld\n",ans);

	return 0;

}