BZOJ 1786 配对(DP)

2023-10-21 02:30

文章标签 dp bzoj 配对 1786

本文主要是介绍BZOJ 1786 配对(DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

如果我们直接令dp[i][j]为前i个位置第i个位置填j所产生的逆序对的最少数。这样是不满足无后效性的。

但是如果发现对于两个-1，如果前面的-1填的数要大于后面的-1填的数。容易证明把他们两交换结果不会变差。

所以对于所有的-1，填的数一定是一个非递减的。

现在我们考虑每个位置对答案的贡献。显然数字位和数字位的逆序对数可以预处理一次算出来。

而-1位和-1位的逆序对数是0，剩下的就是数字位和-1位的逆序对数。

考虑dp[i][j]为前i个-1位第i个-1位填j时产生的逆序对的最少数。这样是没有后效的。有dp[i][j]=min(dp[i][k])+f[j]+t[j].(k<=j).

f[j]表示第i个-1位填j和前面的数字位产生的逆序对总数。t[j]表示第i个-1位填j和后面的数字位产生的逆序对总数。这两个数组可以在一次O(nk)的预处理完成。

dp的复杂度是O(nk).所以总复杂度是O(nk).

# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi 3.1415926535
# define eps 1e-9
# define MOD 100000007
# define INF 1000000000
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {int res=0, flag=0;char ch;if((ch=getchar())=='-') flag=1;else if(ch>='0'&&ch<='9') res=ch-'0';while((ch=getchar())>='0'&&ch<='9')  res=res*10+(ch-'0');return flag?-res:res;
}
void Out(int a) {if(a<0) {putchar('-'); a=-a;}if(a>=10) Out(a/10);putchar(a%10+'0');
}
const int N=10005;
//Code begin...int a[N], res, f[N][105], t[N][105], dp[N][105], mi[N][105];int main ()
{int n, k, ans=INF;scanf("%d%d",&n,&k);FOR(i,1,n) scanf("%d",a+i);FOR(i,1,k) FOR(j,1,n) {if (j>1&&a[j-1]==-1) f[j][i]=f[j-1][i];else if (j>1&&a[j-1]!=-1) f[j][i]=f[j-1][i]+(i<a[j-1]);}FOR(i,1,k) for (int j=n; j>=1; --j) {if (j<n&&a[j+1]==-1) t[j][i]=t[j+1][i];else if (j<n&&a[j+1]!=-1) t[j][i]=t[j+1][i]+(i>a[j+1]);}int pos=0;FOR(i,1,n) {if (a[i]!=-1) {res+=f[i][a[i]]; continue;}++pos;FOR(j,1,k) {dp[pos][j]=mi[pos-1][j]+f[i][j]+t[i][j];if (j>1) mi[pos][j]=min(dp[pos][j],mi[pos][j-1]);else mi[pos][j]=dp[pos][j];}}FOR(j,1,k) ans=min(ans,dp[pos][j]);printf("%d\n",ans+res);return 0;
}