题解 P5574 【[CmdOI2019]任务分配问题】

· · 题解

官方题解:任务分配问题

人话题面: 给一个序列分成k段,让每段内顺序对总和最小。

一道十分套路的DP题。

1~#2

只有一个CPU,写一个树状数组求顺序对就好了,不再赘述。

3

只有两个CPU,枚举分割线取min,树状数组维护两边顺序对即可,不再赘述。

4~#5

不难想到一个dp :

设f[j][i]表示把前i个数分成j段所需的最小代价。

转移 : 设c(i,j)为(i,j]之间的顺序对数,可得:

f[j][i]=\min\limits_{t=1}^{i-1}f[j-1][t]+c(t,i)

如何计算c(t,i)?

注意到,类似莫队,我们能从c(l,r)使用树状数组O(log)推到相邻的区间。

那么我们就倒着来转移,不断加入数字,再更新逆序对数,就能做到转移O(nlogn)了。

总的复杂度是O(n^2klogn)

下面的这份代码可以拿到50pts:

#include<algorithm>
#include<cstdio>
#define lowbit(x) ((x)&-(x))
#define MaxN 40500
using namespace std;
int n,k,a[MaxN],c[MaxN];
void clear(){for (int i=1;i<=n;i++)c[i]=0;}
void add(int pos)
{
  while(pos<=n)
    {c[pos]++;pos+=lowbit(pos);}
}
int query(int pos)
{
  int sum=0;
  while(pos)
    {sum+=c[pos];pos^=lowbit(pos);}
  return sum;
}
long long f[45][MaxN];
int main()
{
  scanf("%d%d",&n,&k);
  for (int i=1;i<=n;i++)scanf("%d",&a[i]);
  long long sav=0;
  for (int i=1;i<=n;i++){
    sav+=query(a[i]);
    f[1][i]=sav;
    add(a[i]);
  }if (k==1){printf("%lld",f[1][n]);return 0;}
  for (int j=2;j<k;j++){
    for (int i=j;i<=n;i++){
      clear();sav=0;f[j][i]=1ll<<60;
      add(a[i]);
      for (int t=i-1;t>=j-1;t--){
        f[j][i]=min(f[j][i],f[j-1][t]+sav);
        sav+=i-t-query(a[t]);
        add(a[t]);
      }
    }
  }
  clear();sav=0;f[k][n]=1ll<<60;
  add(a[n]);
  for (int t=n-1;t>=k-1;t--){
    f[k][n]=min(f[k][n],f[k-1][t]+sav);
    sav+=n-t-query(a[t]);
    add(a[t]);
  }printf("%lld",f[k][n]);
  return 0;
}

6~#10

首先你要知道决策单调性是个什么东西,可以看看DP的决策单调性优化总结,或者上网自行百度。

使用50分的暴力把决策点输出一下,你会发现这东西有决策单调性。

感性理解就是 : n个东西逆序对期望O(n^{2-e})个,既然是平方那么肯定要分的尽量平均。

证明:

那么弄一个单调性分治就好了。

至于,c()的求法可以参照CF868F Yet Another Minimization Problem

就是类似于莫队那样暴力跳,复杂度是对的。

总复杂度O(nklog^2n)

#include<algorithm>
#include<cstdio>
#define lowbit(x) ((x)&-(x))
#define MaxN 40500
using namespace std;
int n,k,a[MaxN],c[MaxN];
inline void _del(int pos)
{
  while(pos<=n)
    {--c[pos];pos+=lowbit(pos);}
}
inline void _add(int pos)
{
  while(pos<=n)
    {++c[pos];pos+=lowbit(pos);}
}
inline int _query(int pos)
{
  int sum=0;
  while(pos)
    {sum+=c[pos];pos^=lowbit(pos);}
  return sum;
}
int l=1,r;long long ans;
long long query(int tl,int tr)
{
  while(tl<l){
    ans+=r-l+1;
    ans-=_query(a[--l]);
    _add(a[l]);
  }
  while(r<tr){
    ans+=_query(a[++r]);
    _add(a[r]);
  }
  while(l<tl){
    _del(a[l]);
    ans+=_query(a[l++]);
    ans-=r-l+1;
  }
  while(tr<r){
    _del(a[r]);
    ans-=_query(a[r--]);
  }return ans;
}
int p[27][MaxN];
void solve(long long *f,long long *g,int *sp,int l,int r,int tl,int tr)
{
  int mid=(l+r)>>1,p;
  long long sav;
  f[mid]=1ll<<60;
  for (int i=tl;i<=min(tr,mid-1);i++){
    sav=g[i]+query(i+1,mid);
    if (sav<f[mid])
      { f[mid]=sav; p=i; }
  }sp[mid]=p;
  if (l<mid)solve(f,g,sp,l,mid-1,tl,p);
  if (mid<r)solve(f,g,sp,mid+1,r,p,tr);
}
long long f[27][MaxN];
int main()
{
  scanf("%d%d",&n,&k);
  for (int i=1;i<=n;i++)scanf("%d",&a[i]);
  for (int i=1;i<=n;i++){
    f[1][i]=f[1][i-1]+_query(a[i]);
    _add(a[i]);
  }for (int i=1;i<=n;i++)c[i]=0;
  for (int j=2;j<=k;j++)
    solve(f[j],f[j-1],p[j],j,n,j-1,n);
  printf("%lld",f[k][n]);
  return 0;
}