首页 > ACM题库 > HDU-杭电 > HDU 3779-Railroad-栈-[解题报告]HOJ
2015
04-10

HDU 3779-Railroad-栈-[解题报告]HOJ

Railroad

问题描述 :

A train yard is a complex series of railroad tracks for storing, sorting, or loading/unloading railroad cars. In this problem, the railroad tracks are much simpler, and we are only interested in combining two trains into one.
Soccer
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.

输入:

The input consists of a number of cases. The first line contains two positive integers N1 N2 which are the number of railroad cars in each train. There are at least 1 and at most 1000 railroad cars in each train. The second line contains N1 positive integers (up to 1,000,000) identifying the products on the first train from front of the train to the back of the train. The third line contains N2 positive integers identifying the products on the second train (same format as above). Finally, the fourth line contains N1+N2 positive integers giving the desired order for the departing train (same format as above).

The end of input is indicated by N1 = N2 = 0.

输出:

The input consists of a number of cases. The first line contains two positive integers N1 N2 which are the number of railroad cars in each train. There are at least 1 and at most 1000 railroad cars in each train. The second line contains N1 positive integers (up to 1,000,000) identifying the products on the first train from front of the train to the back of the train. The third line contains N2 positive integers identifying the products on the second train (same format as above). Finally, the fourth line contains N1+N2 positive integers giving the desired order for the departing train (same format as above).

The end of input is indicated by N1 = N2 = 0.

样例输入:

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

样例输出:

possible
not possible

< [if gte mso 9]>MicrosoftInternetExplorer402DocumentNotSpecified7.8Normal0

Railroad

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)


Total Submission(s): 70    Accepted Submission(s): 24

Problem Description

A train yard is a complex series of railroad tracks for storing, sorting, or loading/unloading railroad cars. In this problem, the railroad tracks are much simpler, and we are only interested in combining two trains into one.



Railroad





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 input consists of a number of cases. The first line contains two positive integers N
1
 N
2
 which are the number of railroad cars in each train. There are at least 1 and at most 1000 railroad cars in each train. The second line contains N
1
 positive integers (up to 1,000,000) identifying the products on the first train from front of the train to the back of the train. The third line contains N
2
 positive integers identifying the products on the second train (same format as above). Finally, the fourth line contains N
1
 +N
2
 positive integers giving the desired order for the departing train (same format as above).




The end of input is indicated by N
1
 = N
2
 = 0.

Output

For each case, print on a line possible if it is 
possible
 to produce the desired order, or 
not possible
 if not.

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

昨天的杭电的比赛做的比较悲催,感觉比较烦躁……
这题交了
8
次才想到优化的方法才过的,题意是这样的,有两个铁路,合成一个铁路,在两个铁路上原来 都有一些车,分别是
n1
辆和
n2
辆,然后告诉你这两条铁路上原来车的顺序,再给你希望合成一条铁路后的车的顺序,问你是否可行
……

ps:为神马看到铁路总想起栈??呃
……

显然dfs

……
设一个递归函数
f(int t1,int t2,int t)

t1
是第一条铁路进第
t1
辆火车,
t2
是第二条铁路进第
t2
辆火车,
t
是合并的那条铁路进了几辆火车,所以只需要看合并那条铁路要进的下一辆火车序 号跟第一条的一样和第二条的一样就行了,所以就有如下递归

if(tt==n+m){ok=1; return;}
if(t1<n && a[t1]==c[tt])f(t1+1, t2, tt+1);
if(t2<m && b[t2]==c[tt])f(t1,t2+1,tt+1);


最后看看ok
是不是等于
1
,如果是,表示
possible
,不是表示
not possible
,但是悲催的这样
tle

……



这里需要一个对于俺来说已经好久没接触的东西:记忆化搜索。


p[i][j]
是第一条铁路进了
i
辆,第二条铁路进了
j
辆火车是否搜索过,如果已经搜索过了,那么就置
1
,否则置
0.
然后如果搜索过了,直接
return
就行了





为神马要这个东西捏?


假设有这两条铁路


1 1 2 3


1 2 3 1


最后要合成的铁路是1 1 1 3 2 3 1 2
(显然不成立吧





那么很显然,调用函数的顺序是这个样子的:


f(0,0,0)->f(1,0,1)->f(2,0,2)->
f(2,1,3)


(没满足了呃……

->f(2,0,2)->f(1,0,1)->f(1,1,2)->

f(2,1,3)


(呃……
又来了
……




所以说,要设置一个记忆化搜索的数组p
,这样就能过了
……



最后附上代码……

#include<stdio.h>
int a[1005],b[1005],c[2005];
int p[1005][1005];
int n,m;
int ok;
int t;
void f(int t1,int t2,int tt)
{
int i;
if(ok) return;
if (p[t1][t2]==1) return;
if(tt==n+m)
{
ok=1; return;
}
if(t1<n && a[t1]==c[tt])
{
f(t1+1, t2, tt+1);
}
if(t2<m && b[t2]==c[tt])
{
f(t1,t2+1,tt+1);
}
p[t1][t2]=1;
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m))
{
if(n==0 && m==0) break;
for(i=0; i<n; i++) scanf("%d",&a[i]);
for(i=0; i<m; i++) scanf("%d",&b[i]);
for(i=0; i<n+m; i++) scanf("%d",&c[i]);
ok=0;
for (i=0;i<=n;i++)
{
for (j=0;j<=m;j++)
{
p[i][j]=0;
}
}
f(0,0,0);
if(ok==1)
printf("possible/n");
else
printf("not possible/n");
}
return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/magicnumber/article/details/6190875


  1. 博物说天天鉴定戴胜很烦,然后有人说哪天非要找个戴胜吃夹竹桃天蛾幼虫的图片给博物君辨认(这两者都是很猎奇但是很普遍天天被人@要鉴定的),博物说夹竹桃天蛾幼虫有毒戴胜不会吃,然后就有了童鞋PS了这张图出来。

  2. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.