SSL_2416 条形图

本文主要是介绍SSL_2416 条形图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出一个呈斜三角的东西，例如第一行为3，第二行为2，第三行为1。在里面放棋子，要求上面一行的不能小于下面一行的，求在第一行为n的这个东西里放棋子的方案。

思路

设$f[i][j]$为第i行放第j个的方案，我们可以容易找到动态转移方程$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 条形图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---