NEU1686 Sort(DP 树状数组)

题目链接

题意:题目比较难懂,复制讨论版的内容,为第二个样例的分析:

3

2 1 3

As we know, there are 27 kinds of permutation of {1,2,3} .

They are

{1,1,1}{1,1,2}{1,1,3}{1,2,1}{1,2.2}{1,2,3}{1,3,1}{1,3,2}{1,3,3}

{2,1,1}{2,1,2}{2,1,3}{2,2,1}{2,2,2}{2,2,3}{2,3,1}{2,3,2}{2,3,3}

{3,1,1}{3,1,2}{3,1,3}{3,2,1}{3,2,2}{3,2,3}{3,3,1}{3,3,2}{3,3,3}

Now, define a new way to sort (given in the test case):2 1 3

which means for each permutation above put all the ‘2’ first,

put all the ‘1’ after all the ‘2’, and then put all the ‘3’ after all the ‘1’.

After that, if this kind permutation is in ascending order.It can be count!

So {1,1,1}{1,1,3}{1,3,1}{1,3,3} {2,2,2}{2,2,3}{2,3,2}{2,3,3}

{3,1,1}{3,1,3}{3,2,2}{3,2,3}{3,3,1}{3,3,2}{3,3,3} THIS 15 kinds can be counted.

思路:做这题前先做这道题(UESTC1217)。这题就是UESTC1217的加强版,多了一个DP:cnt[i][j](i个不同的数排j个位置所有的方案数)。比如说1和2两个数排三个位置,可能是112,121,122,211,212,221六种情况。考虑第一位的数字,如果这个数字不同于后面所有的数字,那么后面的数字就是i-1个数排j-1位;否则就是i个数排j-1位。第一个数有i种可能,所以dp[i][j] = i*(dp[i-1][j-1]+dp[i][j-1])。时间复杂度为n^2。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
const int mod = 1e9+7;
int n;
long long a[2016][2016];
long long dp[2016][2016];
long long cnt[2016][2016];

struct node{
    int pos;
    int num;
}N[2016];

bool cmp(node x, node y){
    return x.num < y.num;
}

int lowbit(int x){
    return x&(-x);
}

void add2(int x,int y,int num){
    for(int i = x; i <= n; i += lowbit(i)){
        a[i][y] += num;
        a[i][y] %= mod;
    }
}

long long sum2(int x,int y){
    long long res = 0;
    for(int i = x; i > 0; i -= lowbit(i)){
        res += a[i][y];
        res %= mod;
    }
    return res;
}

int main(){
    //freopen("a.txt", "r", stdin);
    cnt[0][0] = 1;
    for(int i = 1; i <= 2016; i++){
        for(int j = i; j <= 2016; j++){
            cnt[i][j] = i*(cnt[i][j-1]%mod + cnt[i-1][j-1]%mod)%mod;
        }
    }
    while(scanf("%d", &n) != EOF){
        memset(dp, 0, sizeof(dp));
        memset(a, 0, sizeof(a));
        for(int i = 1; i <= n; i++){
            scanf("%d", &N[i].num);
            N[i].pos = i;
        }
        sort(N+1, N+1+n, cmp);
        long long ans = 0;
        add2(1, 0, 1);
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                dp[i][j] = sum2(N[i].pos, j-1);
                dp[i][j] %= mod;
                if(dp[i][j] == 0) break;
                add2(N[i].pos+1, j, dp[i][j]);
                ans += dp[i][j]*cnt[j][n]%mod;
                ans %= mod;
            }

        }
        cout << ans << endl;
    }
    return 0;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 动态规划  树状数组