BZOJ1786: [Ahoi2008]Pair 配对【DP】

dzy posted @ 2013年6月12日 22:21 in BZOJ with tags bzoj dp , 1656 阅读

10000个数。有些数空着给你填。每个数的范围都在1~K内。求出填满后的逆序对的最小值。

很明显这几个填的数是递增的。不然自己就产生逆序对了。(没证明过

先处理出da[i][j]表示i~n中比j大的数,xi[i][j]表示1~i中比j小的数。

f[i][j]表示填到第i个数了,这位填了j所产生的逆序对。

则f[i][j]=min{f[i][k]+da[pos[i]][j]+xi[pos[i]][j]}。然后再加上数列本身的逆序对数就行了。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=1061109567;
int a[10005],da[10005][105],xi[10005][105],p[10005],f[10005][100],n,k,m=0,An=0;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(!~a[i]) p[++m]=i;
    }for(int i=2;i<=n;i++){
        for(int j=1;j<=k;j++) da[i][j]=da[i-1][j];
        if(~a[i-1]) for(int j=1;j<a[i-1];j++) da[i][j]++;
    }for(int i=n-1;i;i--){
        for(int j=1;j<=k;j++) xi[i][j]=xi[i+1][j];
        if(~a[i+1]) for(int j=a[i+1]+1;j<=k;j++) xi[i][j]++;
    }for(int i=1;i<=n;i++) if(~a[i]) An+=da[i][a[i]];
    memset(f,63,sizeof(f));
    for(int i=1;i<=k;i++) f[1][i]=da[p[1]][i]+xi[p[1]][i];
    for(int i=2;i<=m;i++) for(int j=1;j<=k;j++) for(int o=1;o<=j;o++)
        f[i][j]=min(f[i][j],f[i-1][o]+da[p[i]][j]+xi[p[i]][j]);
    int An2=inf;  for(int i=1;i<=k;i++) An2=min(An2,f[m][i]);
    An2=(An2==inf)?0:An2;
    printf("%d\n",An+An2); return 0;
}
Avatar_small
25penny.com 说:
2023年6月09日 17:06

Website does collect your personal information such as name, identity, Gender and would also collect the geographic location. During your visit to our website, there are chances to collect more information without 25penny.com making you directly acknowledged. Website does collect your personal information such as name, identity, Gender and would also collect the geographic location. During your visit to our website, there are chances to collect more information without making you directly acknowledged.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter