题意:

有n(n<=300)只袋鼠，袋鼠i的体积为a_i，口袋大小为bi(a_i>b_i)。

把袋鼠i放入袋鼠j的口袋里。

要求此时袋鼠i和j的口袋里没有袋鼠，且袋鼠i,j不在其它袋鼠口袋里。

不断操作直到不能操作为止，有多少种不同的终止状态，对10⁹+7取模。

分析:

考虑一种合法的终止状态。

一定存在一只袋鼠，比它小的袋鼠都被装了，能装它的袋鼠都装了其它袋鼠。

先将a和b分别排序。

然后枚举这只倒霉的袋鼠i，dp算出方案数。

将a和b都按是否大于a_i分成左右两边。

用f[i][j]表示a中左边前i个与b中左边匹配j对的方案数。

用g[i][j]表示b中右边前i个与a中右边匹配j对的方案数。

枚举a中左边与b中右边匹配的对数k，则这k对有k!种匹配方法。

再乘上ab两边分别匹配的方案数，就是所有的方案数。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>inline void Scan(Q&x){
	char c; while(c=g(),c<48||c>57);
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}

#define rep(i,a,b) for(int i=a;i<b;++i)
#define dat(i,a,b) for(int i=a;i>b;--i)

const int MAXN=305;
const int Mod=1e9+7;

int n,ans;

int fac[MAXN];

int f[MAXN][MAXN],g[MAXN][MAXN];

int a[MAXN],b[MAXN];

inline void Init(){
	Scan(n);
	rep(i,1,n+1){
		Scan(a[i]),Scan(b[i]);
	}
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	fac[0]=1;
	rep(i,1,n+1)
		fac[i]=1ll*fac[i-1]*i%Mod;
}

inline void Solve(){
	rep(wuke,1,n+1){
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		int r=upper_bound(b+1,b+n+1,a[wuke])-b;
		f[0][0]=1;
		rep(i,1,r)
			rep(j,0,i+1){
				f[i][j]=f[i-1][j];
				int x=lower_bound(a+1,a+wuke,b[i])-a-1;
				if(j&&x-j+1>0){
					f[i][j]=(f[i][j]+1ll*f[i-1][j-1]*(x-j+1)%Mod)%Mod;
				}
			}
		g[n+1][0]=1;
		dat(i,n,wuke)
			rep(j,0,n-i+2){
				g[i][j]=g[i+1][j];
				int x=n-(upper_bound(b+r,b+n+1,a[i])-b)+1;
				if(j&&x-j+1>0){
					g[i][j]=(g[i][j]+1ll*g[i+1][j-1]*(x-j+1)%Mod)%Mod;
				}
			}
		int s=min(wuke-1,n-r+1);
		rep(i,0,s+1){
			ans=(ans+1ll*f[r-1][wuke-1-i]*g[wuke+1][n-r+1-i]%Mod*fac[i]%Mod)%Mod;
		}
	}
	printf("%d\n",ans);
}

int main(){
	freopen("kangaroo.in","r",stdin);
	freopen("kangaroo.out","w",stdout);
	Init(); Solve(); return 0;
}

题意:

给出一棵树，最开始只有1个节点。

每个时刻，这棵树会长出一个叶子。

树上每条边都有且只有1种颜色，并且同一种颜色的边都连通。

定义一个点到根的距离为该点到根的路径上的颜色种数。

求每个时刻树上最大距离的最小值。

分析:

考虑每次向上更新dp值，直到更新到根或者不能更新为止。

由树链剖分可知这样做的复杂度是O(nlogn)的。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAXN=1e6+5;

int n;

int dp[MAXN],p[MAXN];

int mx1[MAXN],mx2[MAXN];

int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout); 
	scanf("%d",&n);
	puts("0");
	for(int i=2;i<=n;++i){
		scanf("%d",p+i);
		dp[i]=1;
		int cur=i;
		while(cur!=1){
			int par=p[cur];
			if(dp[cur]>mx1[par]){
				mx2[par]=mx1[par];
				mx1[par]=dp[cur];
			}
			else if(dp[cur]>mx2[par]){
				mx2[par]=dp[cur];
			}
			cur=par;
			int res=max(mx1[cur],mx2[cur]+1);
			if(res==dp[cur])break;
			dp[cur]=res;
		}
		printf("%d\n",mx1[1]);
	}
	return 0;
}

详见zhj的15年集训队论文

Portal

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define rep(i,a,b) for(int i=a;i<b;++i)
typedef long double ld; 

const int MAXN=1000; 

int n,k,cur;

ld dp[2][MAXN];

int main(){
	scanf("%d%d",&n,&k);
	for(int i=n;i;--i){
		cur^=1;
		int B=701;
		rep(j,1,B){
			dp[cur][j]=(dp[cur^1][j]+(1.+j)/2)*j;
			dp[cur][j]+=(dp[cur^1][j+1]+j);
			dp[cur][j]/=j+1;
			dp[cur][j]+=dp[cur^1][j]*(k-1);
			dp[cur][j]/=k;
		}
	}
	ld ans=dp[cur][1]*k;
	printf("%.20f\n",(double)ans);
	return 0;
}