【转载】 点击打开链接
The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.
For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)
You are asked to write a program to find the minimum inversion number out of the above sequences.
For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following:
a1, a2, ..., an-1, an (where m = 0 - the initial seqence)
a2, a3, ..., an, a1 (where m = 1)
a3, a4, ..., an, a1, a2 (where m = 2)
...
an, a1, a2, ..., an-1 (where m = n-1)
You are asked to write a program to find the minimum inversion number out of the above sequences.
10 1 3 6 9 0 8 5 7 4 2
16
【题意】: 求一个序列的最小逆序对个数，（一个长度为N的序列，每次把它的第一个元素拿到最后面，这样循环N次）；
这道题用归并排序做最简单，但是它的耗时比树型DP多，不过树型DP难度太大，线段树做呢，实际上是耗时最多的， 但也才78ms而已，完过。
归并排序做法AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int N=1e4+5;
int n,node[N],m[N],str[N];
int ss,mins;int min(int x,int y)
{return x>y?y:x;
}void Mergee(int first,int mid,int end,int a[])
{int i=first;int j=mid+1;int k=first;while(i<=mid && j<=end){if(a[i]>a[j]){m[k++]=a[j++];ss += mid - i+1 ;}else{m[k++]=a[i++];}}while(i<=mid){m[k++]=a[i++];}while(j<=end){m[k++]=a[j++];}for(int i=first;i<=end;i++)a[i]=m[i];
}void MergeSort(int first,int end,int a[])
{if(first<end){int mid = (first+end)>>1;MergeSort(first,mid,a);MergeSort(mid+1,end,a);Mergee(first,mid,end,a);}
}int main()
{while(~scanf("%d",&n)){for(int i=1;i<=n;i++){scanf("%d",&node[i]);str[i]=node[i];}ss=0;MergeSort(1,n,node);mins=ss;for(int j=1;j<=n;j++){ss += (n-1-2*str[j]);mins=min(ss,mins);}printf("%d\n",mins);}return 0;
}线段树做法AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int N=5005;
int n;
int a[N];struct tree
{int l,r;int step;
}node[N<<2];void build_tree(int ans,int ll,int rr)
{node[ans].l = ll;node[ans].r = rr;node[ans].step=0;if(ll == rr){return ;}int mid = (ll + rr)>>1;build_tree(ans<<1,ll,mid);build_tree(ans<<1|1,mid+1,rr);
}void update(int ans,int ll)
{if(node[ans].l == node[ans].r ){node[ans].step++;return ;}if(ll<=node[ans<<1].r)update(ans<<1,ll);elseupdate(ans<<1|1,ll);node[ans].step = node[ans<<1].step + node[ans<<1|1].step ;
}int query(int ans,int ll)
{if(ll<=node[ans].l)return node[ans].step;if(ll<=node[ans<<1].r)return query(ans<<1,ll)+query(ans<<1|1,ll);elsereturn query(ans<<1|1,ll);
}int min(int x,int y)
{return x>y?y:x;
}int main()
{while(~scanf("%d",&n)){for(int i=0;i<n;i++)scanf("%d",&a[i]);build_tree(1,0,n);int mins=0;for(int i=0;i<n;i++){mins+= query(1,a[i]+1);update(1,a[i]);}int ss=mins;for(int i=0;i<n;i++){ss+=n-a[i]*2-1;mins=min(ss,mins);}printf("%d\n",mins);}return 0;
}
至于树形DP呢，目前还不会，谅解。