打工
题目大意
题目有点长。
数据范围
对于100%的数据，N≤10000。
题解
设Fi,j,k表示当前编号为1~i的人已经完成分配，且分配方案合法，分配了j队，且第1~i的人的编号组成的序列的字典序小于(k=0)或等于(k=1)原序列第1~i个人的编号组成的字典序时，分配的方案数。
转移比较显然，请读者自行思考，也可参考程序。
由于空间复杂度可能很大，需改成滚动数组。
时间复杂度为N2，请注意常数优化。
Code(C++)
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const long long mo=1000007;
long long f[2][10010][2];
long long s[10010],n;
int main()
{
scanf("%lld",&n);
int i,o=0,u=0;
long long m=1,k=0,l=0;
for (i=1;i<=n;i++)
scanf("%lld",&s[i]);
f[0][1][1]=1;
f[0][1][0]=0;
for (i=2;i<=n;i++)
{
u=1-o;
m=max(m,s[i]);
for (l=1;l<=i;l++)
{
f[u][l][1]=0;
f[u][l][0]=(f[o][l][0]*max(k,l-s[i]+1)+(f[o][l][0]+f[o][l][1])*min(l,s[i]-1)+f[o][l-1][0])%mo;
if(l<s[i])f[u][l][0]=f[u][l][0]+f[o][l-1][1];
}
f[u][m][1]=1;
o=u;
}
long long ans=0;
for (i=1;i<=n;i++)
ans=(ans+f[o][i][0]+f[o][i][1])%mo;
printf("%lld",ans);
}
| 
转播
