题意：N个数，按顺序划分为K组，使得逆序对之和最小。
思路：之前能用四边形不等式写的，一般网上都还有DP单调性分治的做法，今天也尝试用后者写（抄）了一遍。即：
分成K组，我们进行K-1次分治，get(l,r,L,R)中如果mid位置的最优解来自MID，那么分别以mid和MID和分界线，有get(l,mid-1,L,MID)；get(mid+1,r,MID,R)；
区间逆序对没有什么特别高效的方法，我们用莫对跑ok了。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=40010; int a[maxn],sum[maxn],dp[maxn],ans[maxn],N,K,ql,qr,cost; inline int query(int x){int res=0;while(x){ res+=sum[x]; x-=(-x)&x;} return res;} inline void add(int x,int val){while(x<=N){ sum[x]+=val; x+=(-x)&x;} } inline void move(int l,int r) { while(ql>l) cost+=query(a[--ql]-1),add(a[ql],1); while(qr<r) cost+=query(N)-query(a[++qr]),add(a[qr],1); while(ql<l) add(a[ql],-1),cost-=query(a[ql++]-1); while(qr>r) add(a[qr],-1),cost-=query(N)-query(a[qr--]); } inline void get(int l,int r,int L,int R) { if(l>r) return ; int mid=(l+r)>>1,Mid; for(int i=min(R+1,mid);i>L;i--){ move(i,mid); if(dp[i-1]+cost<ans[mid]) {ans[mid]=dp[i-1]+cost; Mid=i-1;} } get(l,mid-1,L,Mid); get(mid+1,r,Mid,R); } int main() { scanf("%d%d",&N,&K); rep(i,1,N) scanf("%d",&a[i]); rep(i,1,N) ans[i]=ans[i-1]+query(N)-query(a[i]),add(a[i],1); ql=1; qr=N; cost=ans[N]; rep(i,2,K){ memcpy(dp,ans,sizeof(ans)); //把上一轮的结果复制 memset(ans,0x3f,sizeof(ans)); get(1,N,0,N-1); } printf("%d ",ans[N]); return 0; }
我也写了四边形不等式来优化DP，其他部分一样。 然而T了，估计是莫对跑得太多了。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=40010; int a[maxn],sum[maxn],dp[maxn][11],pos[maxn][11],N,K,ql,qr,cost; inline int query(int x){int res=0;while(x){ res+=sum[x]; x-=(-x)&x;} return res;} inline void add(int x,int val){while(x<=N){ sum[x]+=val; x+=(-x)&x;} } inline void move(int l,int r) { while(ql>l) cost+=query(a[--ql]-1),add(a[ql],1); while(qr<r) cost+=query(N)-query(a[++qr]),add(a[qr],1); while(ql<l) add(a[ql],-1),cost-=query(a[ql++]-1); while(qr>r) add(a[qr],-1),cost-=query(N)-query(a[qr--]); } int main() { scanf("%d%d",&N,&K); rep(i,1,N) scanf("%d",&a[i]); memset(dp,0x3f,sizeof(dp)); dp[0][1]=0; rep(i,1,N) dp[i][1]=dp[i-1][1]+query(N)-query(a[i]),add(a[i],1); ql=1; qr=N; cost=dp[N][1]; rep(i,2,K){ rep(j,1,N){ int L=pos[j][i-1]?pos[j][i-1]:1; int R=pos[j+1][i]?pos[j+1][i]:N-1; rep(k,L,R) { if(k>=j) continue; move(k+1,j); if(dp[j][i]>dp[k][i-1]+cost){ dp[j][i]=dp[k][i-1]+cost; pos[j][i]=k; } } } } printf("%d ",dp[N][K]); return 0; }