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-

# define MOD

# define INF

# 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<<,l,mid

# define rch p<<|,mid+,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=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

int a[N], res, f[N][], t[N][], dp[N][], mi[N][];

int main ()

{

    int n, k, ans=INF;

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

    FOR(i,,n) scanf("%d",a+i);

    FOR(i,,k) FOR(j,,n) {

        if (j>&&a[j-]==-) f[j][i]=f[j-][i];

        else if (j>&&a[j-]!=-) f[j][i]=f[j-][i]+(i<a[j-]);

    }

    FOR(i,,k) for (int j=n; j>=; --j) {

        if (j<n&&a[j+]==-) t[j][i]=t[j+][i];

        else if (j<n&&a[j+]!=-) t[j][i]=t[j+][i]+(i>a[j+]);

    }

    int pos=;

    FOR(i,,n) {

        if (a[i]!=-) {res+=f[i][a[i]]; continue;}

        ++pos;

        FOR(j,,k) {

            dp[pos][j]=mi[pos-][j]+f[i][j]+t[i][j];

            if (j>) mi[pos][j]=min(dp[pos][j],mi[pos][j-]);

            else mi[pos][j]=dp[pos][j];

        }

    }

    FOR(j,,k) ans=min(ans,dp[pos][j]);

    printf("%d\n",ans+res);

    return ;

}

巴特西

BZOJ 1786 配对(DP)

最新文章

热门文章