传送门：http://codeforces.com/gym/100269/attachments
题目大意：
有n个点r[i]，r[i]<=s,每个r[i]有一个权值，权值的规则是在0~i这个区间上比r[i]小的个数。然后要求吧这n个数分成
k部分，每部分的r[i]值是在一个连续的区间内的，但是他们在n数组中的相对位置不变，求总的最小权值是多少。
题解：
首先处理出（以下的“区间”均表示r[i]值的）当区间【i,j】单独一部分的时候的权值sum[i][j]。然后再dp[i][j]表示以i为右端点的区间是第j部分的最小权值和。那么状态转移方程是dp[i][j]=min(dp[t][j-1]+sum[t][i]){t<=i}。
那么怎么处理每段区间的权值呢？从区间【l,r】枚举每次添加一个值到相应的（在原n数组中的位置）位置（这里是添加到树状数组中的位置上了，在该位置+1即可）。然后查询在添加当前值之前该位置以前有几个值了，因为是从小到大插入的所以这之前肯定都比当前值小。dp直接暴力就行了。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <vector> using namespace std; vector<int>ve[1100]; int A[4400],r[1100]; int sum[1100][1100],dp[1100][1100]; int get(int x) { int s=0; while(x>0) { s+=A[x]; x-=x&(-x); } return s; } void updata(int i,int val,int n) { while(i<n) { A[i]+=val; i+=i&(-i); } } int main() { freopen("flight.in","r",stdin); freopen("flight.out","w",stdout); int n,s,k; scanf("%d%d%d",&n,&s,&k); for(int i=1; i<=n; i++) { scanf("%d",&r[i]); ve[r[i]-1].push_back(i); } memset(sum,0,sizeof(sum)); for(int i=0; i<s; i++) { memset(A,0,sizeof(A)); for(int j=i; j<s; j++) { if(i!=j)sum[i][j]=sum[i][j-1]; for(int t=0; t<ve[j].size(); t++) { sum[i][j]+=get(ve[j][t]); } for(int t=0; t<ve[j].size(); t++) { updata(ve[j][t],1,1050); } } } for(int i=0; i<=s; i++) for(int j=0; j<=k; j++) dp[i][j]=1e9; dp[0][0]=0; for(int i=0; i<s; i++) { for(int j=0; j<=k; j++) { for(int t=i; t<s; t++) { dp[t+1][j+1]=min(dp[t+1][j+1],dp[i][j]+sum[i][t]); } } } printf("%d\n",dp[s][k]); return 0; }
