BZOJ 4221 [JOI2012春季合宿]Kangaroo (DP)

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=4221

题解

orz WYC 爆切神仙DP
首先将所有袋鼠按大小排序。考虑从前往后DP, 设$f[i][j]$表示前$i$个元素形成了$j$条链。
然而需要处理“套到不能套为止”的问题，因此再加一维: $k$表示目前有多少个元素确定了必须要套后面的袋鼠。
设$cnt[i]$表示有多少个别的袋鼠能套$i$. 那么从$i-1$转移到$i$时$k$的范围是$[0,cnt[i]-(i-j-1)]$, 因为前$(i-1)$个袋鼠形成了$j$条链，有$(i-j-1)$个袋鼠已经套上了，由于袋鼠是从大到小排的，那么能套上$i$之前的袋鼠就能套$i$, 因此$(i-j-1)$就是能套上$i$且套了的袋鼠个数，$cnt[i]-(i-j-1)$就是能套上$i$且还没套的袋鼠个数。
转移:
(1) 这个点作为链的起点。这样会导致任何没套上袋鼠的袋鼠都要再套一个比$i$小的袋鼠，因此转移到$dp[i][j+1][cnt[i]-(i-j-1)]$.
(2) 插入到一个链的末尾。这个链有可能是必须要套后面的袋鼠也有可能不是。乘上相应的系数转移即可。
时间复杂度$O(n^{3)$.

据说有神仙$O(n}2)$做法……哪位大爷教教我啊

代码

#include<bits/stdc++.h>

#define llong long long

using namespace std;

const int N = 300;

const int P = 1e9+7;

struct Element

{

    int a,b;

    bool operator <(const Element &arg) const {return a>arg.a;}

} a[N+3];

int cnt[N+3];

llong dp[2][N+3][N+3];

int n;

void updsum(llong &x,llong y) {x = (x+y)%P;}

int main()

{

    scanf("%d",&n);

    for(int i=1; i<=n; i++) scanf("%d%d",&a[i].a,&a[i].b);

    sort(a+1,a+n+1);

    for(int i=1; i<=n; i++) {for(int j=1; j<i; j++) {if(a[j].b>a[i].a) cnt[i]++;}}

    dp[0][0][0] = 1ll; int cur = 0,nxt = 1;

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

    {

        memset(dp[nxt],0,sizeof(dp[nxt]));

        for(int j=0; j<=i; j++)

        {

            for(int k=0; k<=cnt[i]-(i-j-1); k++)

            {

                if(dp[cur][j][k])

                {

                    updsum(dp[nxt][j][k],dp[cur][j][k]*(cnt[i]-(i-j-1)-k));

                    if(k) {updsum(dp[nxt][j][k-1],dp[cur][j][k]*k);}

                    updsum(dp[nxt][j+1][cnt[i]-(i-j-1)],dp[cur][j][k]);

                }

            }

        }

        cur^=1,nxt^=1;

    }

    llong ans = 0ll;

    for(int i=0; i<=n; i++) {ans = (ans+dp[cur][i][0])%P;}

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

    return 0;

}

巴特西

BZOJ 4221 [JOI2012春季合宿]Kangaroo (DP)

题目链接

题解

代码

最新文章

热门文章