【Codeforces 8VC Venture Cup 2016 - Elimination Round】F Group Projects
Zarxdy34
posted @ 2016年3月01日 18:42
in Codeforces
with tags
DP
, 594 阅读
这是一道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.
\]
\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;
}
评论 (0)
