本文主要是介绍SSL_2416 条形图,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意
给出一个呈斜三角的东西,例如第一行为3,第二行为2,第三行为1。在里面放棋子,要求上面一行的不能小于下面一行的,求在第一行为n的这个东西里放棋子的方案。
思路
设 f[i][j] f [ i ] [ j ] 为第i行放第j个的方案,我们可以容易找到动态转移方程 f[i][j]=f[i−1][j]+f[i][j−1] f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i ] [ j − 1 ] ,用高精度就可以求出来了。
代码
#include<cstdio>
int n,t,f[101][101][101],ans[101];
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++) f[i][0][100]=1;for (int i=1;i<=n;i++)for (int j=1;j<=i;j++){t=0;for (int k=100;k>=1;k--){f[i][j][k]=f[i][j-1][k]+f[i-1][j][k]+t;t=f[i][j][k]/10;f[i][j][k]%=10;}}for (int i=1;i<=n;i++)//最后把f[n][1~n]的答案都统计起来{t=0;for (int j=100;j>=1;j--){ans[j]=ans[j]+f[n][i][j]+t;t=ans[j]/10;ans[j]%=10;}}int i=1;while (ans[i]==0&&i<=99) i++;for (;i<=100;i++) printf("%d",ans[i]);
}
这篇关于SSL_2416 条形图的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!