【Codeforces 8VC Venture Cup 2016 - Elimination Round 】E Simple Skewness
【Codeforces 8VC Venture Cup 2016 - Elimination Round】G Raffles

【Codeforces 8VC Venture Cup 2016 - Elimination Round】F Group Projects

Zarxdy34 posted @ 2016年3月01日 18:42 in Codeforces with tags DP , 565 阅读

  这是一道DP题,然而我考的时候完全没有想到。

  首先将所有人从小到大排个序。\(f[i][j][l]\)表示前i个学生已经完成分组,分成的组有j个是开区间(最小的学生已经确定下来了,但是最大的还没有确定下来的组是一个开区间),当前的总的不平衡度至少为l。关于这个l,由于有一些区间是开区间,后面加进来的学生对这些开区间的贡献一定是会变大(或者不变)的,这里用到了差分的思想。

  每次新加进来一个学生i,这时的不平衡度为\(l + j*(a[i] - a[i - 1])\)(因为有j个开区间,利用差分的思想,这些开区间每个都要加上\(a[i] - a[i - 1]\))。接下来分四种情况:

  1.把这个学生单独分成一组闭区间,此时j不变

  2.把这个学生单独分成一组开区间,此时开区间数j加一个

  3.把这个学生分进j组中的任意一组,并保持该组是开区间,此时j不变

  4.把这个学生分进j组中的任意一组,并保持该组是闭区间,此时开区间数j减一个

  至此状态转移方程应该是比较明朗的了。

  设\(nextl=l+j*(a[i]-a[i-1])\),那么有\(f[i][j][k]\)的转移方程为

\[
\left\{ \begin{array}{l}
f[i - 1][j][nextl]\\
f[i - 1][j + 1][nextl]\\
f[i - 1][j][nextl]*j\\
f[i - 1][j - 1][nextl]*j,j > 0
\end{array} \right.
\]
 
  然后用滚动数组就好了。
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int maxn=210,maxk=1010,p=1e9+7;

int f[2][maxn][maxk];
int a[maxn];
int n,k;

int main()
{
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	int o=0;f[0][0][0]=1;
	for (int stu=1;stu<=n;stu++)
	{
		o^=1;
		memset(f[o],0,sizeof(f[o]));
		for (int i=0;i<stu;i++)
			for (int j=0;j<=k;j++)
			{
				int fo=f[o^1][i][j],b=j+i*(a[stu]-a[stu-1]);
				if (b>k || !fo) continue;
				if (i) (f[o][i-1][b]+=(LL)i*fo%p)%=p;
				(f[o][i][b]+=(LL)(i+1)*fo%p)%=p;
				if (i+1<=n) (f[o][i+1][b]+=fo)%=p;
			}
	}
	int ans=0;
	for (int i=0;i<=k;i++) (ans+=f[o][0][i])%=p;
	printf("%d\n",ans);
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter