如果我们直接令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 ",ans+res); return 0; }