[JOI2012]kangaroo

本文主要是介绍[JOI2012]kangaroo，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

kangaroo

题解

dp板子。

首先我们应该是很容易想到将口袋与球分开处理，因为自己的口袋是肯定装不下自己的，所以分开处理也不会有任何偏差。
所以我们很快想到将所有的口袋与球根据大小排序后做dp，保证前面的一定装不下后面的，这样dp也就很好想了。
令$d{p}_{i,j,k}$表示已经处理了前$i$个，剩下$j$个口袋永远不会选，$k$个口袋会在后面的过程中被选择的方案数。
由于为保证在之后不会被选择的口袋数量，我们需要让一部分口袋牺牲一下，所以要将这两种口袋分开处理。
dp方程式也是非常好想的。
当加入球时，明显此时如果有永远不选口袋剩着就一定会被选择，转移为
$d{p}_{i,j,k}=(k+1)d{p}_{i-1,j,k+1}+d{p}_{i-1,0,k}$
加入口袋的转移为
$d{p}_{i,j,k}=d{p}_{i-1,j-1,k}+d{p}_{i-1,j,k-1}$
跑一下就可以了。

总时间复杂度$O\left(n^3\right)$。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
#define MAXN 605
#define lowbit(x) (x&-x)
#define reg register
typedef long long LL;
const int mo=1e9+7;
typedef unsigned long long uLL;
typedef pair<LL,LL> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
int n,dp[MAXN][MAXN/2][MAXN/2],tot,ans;
struct ming{int val,typ;}s[MAXN];
bool cmp(ming x,ming y){if(x.val==y.val)return x.typ<y.typ;return x.val>y.val;
}
int add(int x,int y){return x+y<mo?x+y:x+y-mo;}
signed main(){read(n);int sum=0;dp[0][0][0]=1;for(int i=1;i<=n;i++){int a,b;read(a);read(b);s[++tot]=(ming){a,1};s[++tot]=(ming){b-1,0};}sort(s+1,s+tot+1,cmp);for(int i=1;i<=tot;i++)if(s[i].typ)for(int j=0;j<=sum;j++)for(int k=0;j+k<=sum;k++){dp[i][j][k]=add(dp[i][j][k],1ll*(k+1)*dp[i-1][j][k+1]%mo);if(!j)dp[i][j][k]=add(dp[i][j][k],dp[i-1][j][k]);}else{sum++;for(int j=0;j<=sum;j++)for(int k=0;j+k<=sum;k++){if(j)dp[i][j][k]=add(dp[i][j][k],dp[i-1][j-1][k]);if(k)dp[i][j][k]=add(dp[i][j][k],dp[i-1][j][k-1]);}}for(int i=0;i<=sum;i++)ans=add(ans,dp[tot][i][0]);printf("%d\n",ans);return 0;
}

谢谢！！！

这篇关于[JOI2012]kangaroo的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---