[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();
}
}