C - K-inversions URAL - 1523 (dp + 线段树)

题目链接：https://cn.vjudge.net/contest/275079#problem/C

具体思路：我们可以分层的去建立，假设我们要找ｋ层，我们可以先把满足１．２．．．．ｋ-1层的满足情况的找出来，然后就可以求出ｋ层的了．这个过程需要线段树的维护，每一次我们先找出当前这个在满足情况下的个数，然后不停的往下跟新就可以了．

ＡＣ代码：

#include<iostream>

#include<cstring>

#include<iomanip>

#include<stdio.h>

#include<cmath>

using namespace std;

# define inf 0x3f3f3f3f

# define ll long long

const int mod = 1e9 ;

const int maxn = 100000+100;

ll a[maxn];

ll ans[maxn];

ll dp[maxn][100];

ll n,m;

int lowbit(int t)

{

    return t&(-t);

}

void update(int t,int d)

{

    while(t<=n)

    {

        a[t]=(a[t]+d)%mod;

        t+=lowbit(t);

    }

}

int query(int t)

{

    ll ans=0;

    while(t>0)

    {

        ans=(ans+a[t])%mod;

        t-=lowbit(t);

    }

    return ans;

}

int main()

{

    scanf("%lld %lld",&n,&m);

    for(int i=1; i<=n; i++)

    {

        scanf("%lld",&ans[i]);

    }

    for(int i=1; i<=n; i++)

    {

        dp[i][1]=1;

    }

    for( int i=2; i<=m; i++)

    {

        memset(a,0,sizeof(a));

        for(int j=1; j<=n; j++)

        {

            dp[j][i]=(mod+query(n)-query(ans[j]))%mod;//　每一次寻找

            update(ans[j],dp[j][i-1]);

        }

    }

    ll sum=0;

    for(int i=1; i<=n; i++)

    {

        sum=(sum+dp[i][m]+mod)%mod;

    }

    printf("%lld\n",sum);

    return 0;

}

巴特西

C - K-inversions URAL - 1523 (dp + 线段树)

最新文章

热门文章