[FOJ1902 Graduate]动态规划

【题目大意】
给出N个人,他们高度各不相同,让他们站两排,满足:
1、同一个位置的人中,前面的比后面的矮。
2、最终没有一排是空的,而且后面那排的人数<=前面那排。
3、如果i站在j的左边,那么i比j矮。
问有多少种方案。
结果mod 20100501
【算法分析】
dp
F[i][j]表示前面那排排了i个人,后面那排排了j个人。
那么方程就是F[i][j]=F[i-1][j]+F[i,j-1]。(i>=j && i+j<=n)
初始F[0][0]=1。
【时间复杂度】O(n^2)
【CODE】
#include #include #include int a[105];
int f[105][105];

void init(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
}

void dp(){
memset(f,0,sizeof(f));
f[0][0]=1;
int i,j;
for (i=0;i<=n;i++)
for (j=0;i+j<=n && j<=i;j++)
if (i+j>0){
if (i) f[i][j]+=f[i-1][j];
if (j) f[i][j]+=f[i][j-1];
f[i][j]%=20100501;
}
int ans=0;
for (i=1;i<=n/2;i++){
ans+=f[n-i][i];
ans%=20100501;
}
printf("%dn",ans);
}

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
printf("Case #%d: ",i);
init();
dp();
}
}

加入对话

3条评论

  1. 回复卡通BlueEye:因为可以看成那些人是从小到大给你的,只要任意时刻,i>=j,就可以保证前面那个人的高度一定比后面这个人小。

留下评论

您的电子邮箱地址不会被公开。