首页 > 其他 > 详细

洛谷P1044 栈

时间:2018-07-05 23:05:54      阅读:171      评论:0      收藏:0      [点我收藏+]

之前看这题还是一头雾水,现在看:啊啊啊lydnb!

思考了一段时间,发现可以用DP。

令f[i]表示有i辆车时的方案术。

我一开始考虑的是在后面加车,可是这样搞不出状态转移方程来。

然后我考虑从前面加,问题迎刃而解!

考虑加在前面的那一辆车的出栈时机,这样就可以用 f[前] * f[后] 来转移了。

技术分享图片
 1 #include <cstdio>
 2 typedef long long LL;
 3 const int N = 22;
 4 
 5 LL f[N];
 6 
 7 int main() {
 8     int n;
 9     scanf("%d", &n);
10     f[1] = f[0] = 1;
11     for(int i = 2; i <= n; i++) {
12         for(int j = 0; j < i; j++) {
13             f[i] += f[j] * f[i - 1 - j];
14         }
15     }
16     printf("%lld", f[n]);
17     return 0;
18 }
AC代码

 

洛谷P1044 栈

原文:https://www.cnblogs.com/huyufeifei/p/9270517.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!