HDU 3779 Railroad(记忆化搜索)
Railroad
Time Limit : 4000/2000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 10 Accepted Submission(s) : 3
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Figure 1: Merging railroad tracks.
The two trains each contain some railroad cars. Each railroad car contains a single type of products identified by a positive integer up to 1,000,000. The two trains come in from the right on separate tracks, as in the diagram above. To combine the two trains, we may choose to take the railroad car at the front of either train and attach it to the back of the train being formed on the left. Of course, if we have already moved all the railroad cars from one train, then all remaining cars from the other train will be moved to the left one at a time. All railroad cars must be moved to the left eventually. Depending on which train on the right is selected at each step, we will obtain different arrangements for the departing train on the left. For example, we may obtain the order 1,1,1,2,2,2 by always choosing the top train until all of its cars have been moved. We may also obtain the order 2,1,2,1,2,1 by alternately choosing railroad cars from the two trains.
To facilitate further processing at the other train yards later on in the trip (and also at the destination), the supervisor at the train yard has been given an ordering of the products desired for the departing train. In this problem, you must decide whether it is possible to obtain the desired ordering, given the orders of the products for the two trains arriving at the train yard.
Input
The end of input is indicated by N1 = N2 = 0.
Output
Sample Input
3 3
1 2 1
2 1 1
1 2 1 1 2 1
3 3
1 2 1
2 1 2
1 1 1 2 2 2
0 0
Sample Output
possible
not possible
Source
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int n,m;
int a[],b[],c[];
bool vis[][];
bool dfs(int x,int y,int k)
{
if (k==n+m+) return ;
if(vis[x][y]) return ;
vis[x][y]=;
if (x<=n && a[x]==c[k] && dfs(x+,y,k+))
return ;
if (y<=m && b[y]==c[k] && dfs(x,y+,k+))
return ; return ;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if (n== && m==) break;
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=m;i++) scanf("%d",&b[i]);
for(int i=;i<=n+m;i++)scanf("%d",&c[i]);
memset(vis,,sizeof(vis));
if (dfs(,,)) printf("possible\n");
else printf("not possible\n");
}
return ;
}
最新文章
- ComboBox,三级联动菜单,新入门点小白,有些代码有待优化,大神勿喷
- [普通平衡树treap]【学习笔记】
- mysql 控制台上传数据库
- DrawerLayout的使用
- Redis设计与实现-附加功能
- js:数据结构笔记3--栈
- 在csdn里markdown感受
- poj 1125 Stockbroker Grapevine dijkstra算法实现最短路径
- 115 Java Interview Questions and Answers – The ULTIMATE List--reference
- codeforces Vasya and Digital Root
- devexpress实现单元格合并以及依据条件合并单元格
- js简单省级联动菜单
- 《算法4》读书笔记 1.4 - 算法分析(Analysis of Algorithm)
- VB.NET 打开窗体后关闭自己
- 实验:实现https
- linux下安装jdk,tomcat以及mysql
- nginx开机启动
- 参考RPC
- go标准库的学习-crypto/md5
- memcached 一致性哈希算法