【原题】

Description

Input

Output

Sample Input

Sample Output

HINT

Source

Day1

【分析】一看到就感觉有思路，好像-1的格子有什么规律。于是开始YY。

简单的脑补：设A,B,C三个点，A,C是-1。显然，A、C的大小关系和A左边、B右边的无关。

若A<=C。如果B>C逆序对就是1 ，否则是0。

若A>C。如果B>C逆序对就是2 ，否则是1。

显然-1的格子是单调上升的最好。

然后的DP真的是太水了。先求出原来数的逆序对个数，然后只考虑-1的点造成的逆序对增量。

设f[i][j]是到第i个-1的点，改成数字j的最少逆序增量。显然f[i][j]=min(f[i-1][k]+cost)。而代价是1--i中比j大的数和i+1--n中比j小的数的和。可以先预处理出来。

还有，根据这个方程，除了状压外，还可以把时间效率从NK^2压成NK。

【造数据程序】无限WA！于是就找了个标程对拍。

#include
  
   
#include
   
     #include
    
      using namespace std; int main() { freopen("1786.in","w",stdout); srand((int)time(0)); int n=1000,k=100; printf("%d %d\n",n,k); for (int i=1;i<=n;i++) { int num=rand()%10; if (!num) printf("-1 ");else printf("%d ",rand()%10+1); } return 0; }
    
   
  

好不容易发现错误：最后更新Min的时候我用f数组。看上去因为f和g是一样的（memcpy），但其实如果-1只有1个，就不会有f了，而边界条件是g。于是应该改用g来更新Min。

【代码】

#include
  
   
#include
   
     #include
    
      #define N 10005 #define K 105 using namespace std; int place[N],big[N][K],small[N][K],f[K],g[K],a[N]; int n,L,i,j,m,now,last,ans,Min; int main() { freopen("1786.in","r",stdin); freopen("1786.out","w",stdout); scanf("%d%d",&n,&L); for (i=1;i<=n;i++) {scanf("%d",&a[i]);if (a[i]==-1) place[++m]=i;} for (i=2;i<=n;i++) { memcpy(big[i],big[i-1],sizeof(big[i-1])); if (a[i-1]>-1) for (j=1;j
     
      -1) for (j=L;j>a[i+1];j--) small[i][j]++; } for (i=1;i<=n;i++) if (a[i]>-1) ans+=small[i][a[i]]; for (i=1;i<=L;i++) g[i]=big[place[1]][i]+small[place[1]][i]; for (i=2;i<=m;i++) { for (last=2;last<=L;last++) g[last]=min(g[last],g[last-1]); for (now=1;now<=L;now++) f[now]=g[now]+big[place[i]][now]+small[place[i]][now]; memcpy(g,f,sizeof(f)); } Min=g[1];for (i=2;i<=L;i++) Min=min(Min,g[i]); printf("%d",ans+Min); return 0; }