地铁重组

题目描述
问题描述
蒙提在暴风城与铁炉堡之间的地铁站中工作了许多年，除了每天抓一些矿道老鼠外，没有其他的变化。然而最近地铁站终于要扩建了，因为侏儒们攻克了建设长距离穿海隧道的技术难题，矮人们制造的炸药威力也有了很大的增强。于是，联盟决定修建通往诺森德的地铁。拥有常年的地铁站工作经验的蒙提被派往了新的线路上，他的工作是进行地铁重组。

如上图，在左边部分停靠着N节车厢，从右向左标号依次为1、2、……、N。中间有一个停车轨道，这个轨道上最多只能同时停放P节车厢。现在需要将左边轨道上的车厢驶入右边的轨道。每节车厢必须进入一次停车轨道进行检修，然后才能去右边的轨道。侏儒制造的每节车厢都有完整的动力装置，不需要依赖车头的带动。对于一个给定的停车轨道的大小P和左边轨道的车厢的数目N，蒙提想知道，这些车厢到右边轨道以后，有多少种不同的排列顺序。

输入
第1行：两个整数N,P。
输出
第1行：一个整数a，为排列顺序数除以4096的余数。
输入样例
3 2

输出样例
4

说明
数据规模
对于70%的数据

1 <= N <= 500
1 <= P <= 300

对于100%的数据
1 <= N <= 2000
1 <= P <= 2000

.
.
.
.
.
分析
F[i][j]表示左边有i个 栈中有j个时的状态 最终状态为F[0][0]
F[i][j]+=F[i][j+1]+F[i+1][j-1]

.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> using namespace std;int n,p,f[2010][2010];int main() {scanf("%d%d",&n,&p);memset(f,0,sizeof(f));f[n][0]=1;for (int i=n-1;i>=0;i--)for (int j=min(p,n-i);j>=0;j--){f[i][j]=f[i][j+1]%4096;if (j>=1) f[i][j]+=f[i+1][j-1]%4096;f[i][j]%=4096;}printf("%d",f[0][0]%4096);return 0; }

转载于:https://www.cnblogs.com/YYC-0304/p/11094921.html

总结

以上是生活随笔为你收集整理的地铁重组的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。