TopCoder SRM 489 Div1 Lev3：AppleTree

挺优秀的一道题，想出做法时有些惊艳。

题意：

数轴上有\(D\)个连续整数刻度，有\(N\)棵树要种在这些刻度上，其中第\(i\)棵与两旁（如果有的话）相邻的树至少要相距\(R_i\)，问方法数。

\(1 \leq N , R_i \leq 40\)

思路：

首先，如果确定了种树的顺序，就确定了相邻树的最小间距。把\(D\)减掉最小间距之和，所得的就是“冗余刻度”的数量。

把这个数量分配给\(N+1\)段间隙，用插板法可以求出方法数。

所以问题在于，对于每一个\(L\)，求出1到\(N\)的排列\(P\)的数量，满足：

\[\sum_{i=1}^{N-1} \mathrm{max}(R_{P_i}, R_{P_{i+1}})=L
\]

注意到，对于使\(R_i\)最大的\(i\)，它的两侧种的是什么树，不影响这两段间隙的最小长度。

根据套路，这个时候我们应该在\(i\)的位置把排列割开并分别处理。

对于一个1到\(N\)的子集的长度为\(l\)的排列\(P\)，定义其代价为：\(\sum_{i=1}^{l-1} \mathrm{max}(R_{P_i}, R_{P_{i+1}})\)。

我们先把\(R\)数组从小到大排序，接着DP：\(dp[i][j][k]\)表示，1到\(i\)这\(i\)个数，组成了\(j\)个不相交排列，排列的代价总和为\(k\)的方法数。

转移时考虑第\(i\)个数在一个排列的两端还是中间，删除之，加上第\(i\)个数两侧的空隙长度并转移即可。把树排序的意义在于，排序后第\(i\)棵树一定是\([1,i]\)中\(R\)值最大的那个。

注意到\(i,j \leq 40\)，\(k \leq 1600\)，故复杂度没有问题。

等等，正确性有问题……

因为长度为1的排列只有一个端点，而在先前的状态中很难区分长度为1和大于1的排列，故无法求出转移时乘的系数。

所以不妨直接考虑从长度为1的那些排列入手，发现……可以用它们合并成更长的排列？

于是想到可以DP状态不变，转移做如下修改：

首先，初始状态\(dp[0][0][0]=1\)。

其次，允许通过以下方式转移：

1、把\(i+1\)单独组成一个长为1的排列

2、任选两个排列，把\(i\)放在中间将其连接

3、任选一个排列，把\(i\)吸附在其端点旁边

这样把\(i+1\)添加进当前的排列集合之后，就可以转移到\(i'=i+1\)的情况。

对于每一个\(L\)，求出1到\(N\)的排列\(P\)的数量，满足\(\sum_{i=1}^{N-1} \mathrm{max}(R_{P_i}, R_{P_{i+1}})=L\)

而对于每一个\(L\)，要求的值就是\(dp[N][1][L]\)。Bingo！

代码：

// BEGIN CUT HERE

// END CUT HERE

#line 5 "AppleTrees.cpp"

#include <bits/stdc++.h>

using namespace std;

#define iinf 2000000000

#define linf 1000000000000000000LL

#define ulinf 10000000000000000000ull

#define MOD 1000000007LL

#define lson(v) ((v)<<1)

#define rson(v) (((v)<<1)^1)

#define mpr make_pair

typedef long long LL;

typedef unsigned long long ULL;

typedef unsigned long UL;

typedef unsigned short US;

typedef pair < int , int > pii;

clock_t __stt;

inline void TStart(){__stt=clock();}

inline void TReport(){printf("\nTaken Time : %.3lf sec\n",(double)(clock()-__stt)/CLOCKS_PER_SEC);}

template < typename T > T MIN(T a,T b){return a<b?a:b;}

template < typename T > T MAX(T a,T b){return a>b?a:b;}

template < typename T > T ABS(T a){return a>0?a:(-a);}

template < typename T > void UMIN(T &a,T b){if(b<a) a=b;}

template < typename T > void UMAX(T &a,T b){if(b>a) a=b;}

int n,dp[42][42][1655],fac[100005];

int inv(int val){

	int ret=1,tms=MOD-2;

	while(tms){

		if(tms&1) ret=((LL)ret*(LL)val)%MOD;

		val=((LL)val*(LL)val)%MOD;

		tms>>=1;

	}

	return ret;

}

int C(int n,int m){

	if(n<m) return 0;

	if(!n) return 1;

	int u=fac[n],d=((LL)fac[m]*(LL)fac[n-m])%MOD;

	return ((LL)u*(LL)inv(d))%MOD;

}

class AppleTrees {

	public:

	int theCount(int D, vector <int> r){

		sort(r.begin(),r.end());

		n=(int)r.size();

		int i,j,k,res=0;

		fac[0]=1;

		for(i=1;i<=D;++i){

			fac[i]=((LL)fac[i-1]*(LL)i)%MOD;

		}

		dp[0][0][0]=1;

		for(i=0;i<n;++i){

			for(j=0;j<=n;++j){

				for(k=0;k<=1620 && k<=D;++k){

					if(!dp[i][j][k]) continue;

					dp[i+1][j+1][k]+=dp[i][j][k];

					dp[i+1][j+1][k]%=MOD;

					dp[i+1][j][k+r[i]]+=((LL)dp[i][j][k]*2LL*(LL)j)%MOD;

					dp[i+1][j][k+r[i]]%=MOD;

					if(j>1){

						dp[i+1][j-1][k+2*r[i]]+=((LL)dp[i][j][k]*(LL)j*(LL)(j-1))%MOD;

						dp[i+1][j-1][k+2*r[i]]%=MOD;

					}

				}

			}

		}

		for(i=1;i<=1620 && i<=D;++i){

			res+=((LL)dp[n][1][i-1]*(LL)C(D-i+n,n))%MOD;

			res%=MOD;

		}

		return res;

	}

};

巴特西

TopCoder SRM 489 Div1 Lev3：AppleTree

题意：

思路：

代码：

最新文章

热门文章