题目链接：http://codeforces.com/gym/100269
题意：
现在有n个人，s个位置和你可以划分长k个区域

你可以把s个位置划分成k个区域，这样每个人坐下你的代价是该区域内，在你之前比你小的人的数量

问你怎么划分这s个位置（当然，每个区域必须是连续的），才能使得总代价最小

输出代价

话说这个题真是读了好久好久

解法：

数据范围1000，显然的dp

dp[i][j]表示第i个位置是第j个区域的结尾，然后暴力转移就好了

用树状数组预处理sum[i][j]，表示第i个位置和第j个位置划分在一起的代价是多少

复杂度 O(m*m*k + m*m*logm)

//CF GYM 100269

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1050;
int dp[maxn][55];///dp[i][j]表示第i个位置是第j个区域的结尾
int sum[maxn][maxn];///表示第i个位置和第j个位置划分在一起的代价是多少
int r[maxn];
int n, m, k;

vector <int> E[maxn];

namespace BIT{
    int c[maxn];
    inline int lowbit(int x){return x&-x;}
    inline void update(int i, int v){for(; i < maxn; i += lowbit(i)) c[i] += v;}
    inline int query(int i){int res = 0; for(; i; i-=lowbit(i)) res += c[i]; return res;}
} using namespace BIT;

int main()
{
    freopen("flight.in","r",stdin);
    freopen("flight.out","w",stdout);
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i++){
        scanf("%d", &r[i]);
        E[r[i]-1].push_back(i);
    }
    for(int i = 0; i < m; i++){
        memset(c, 0, sizeof(c));
        for(int j = i; j < m; j++){
            if(i != j) sum[i][j] = sum[i][j-1];
            for(int t = 0; t < E[j].size(); t++){
                sum[i][j] += query(E[j][t]);
            }
            for(int t = 0; t < E[j].size(); t++){
                update(E[j][t], 1);
            }
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < k; j++){
            if(dp[i][j] == 0x3f) continue;
            for(int t = i; t < m; t++){
                dp[t+1][j+1] = min(dp[t+1][j+1], dp[i][j] + sum[i][t]);
            }
        }
    }
    printf("%d\n", dp[m][k]);
    return 0;
}