hdu---(3779)Railroad(记忆化搜索/dfs)

Railroad

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 572    Accepted Submission(s): 228

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.

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 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.

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

题目的意思:  给你两个数组a,b  让a,b两个数组按其原序进行组合,问能否组合成为c数组。

我们可以试着用搜索的方式进行处理,但是由于数据较大,而且在处理的过程中,有重叠的状态,所以我们需要用到记忆话,对于原先有的状态之后的搜索,我们不去在重复,这样就节省了很多的时间。

代码:

 1 //#define LOCAL
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=1002;
 6 int aa[maxn],bb[maxn],cc[maxn<<1];
 7 int mat[maxn][maxn];
 8 int n1,n2;
 9 bool flag;
10 void dfs(int lena,int lenb,int lenc)
11 {
12     if(lena==n1+1&&lenb==n2+1){
13          flag=1;
14         return ;
15      }
16    if(mat[lena][lenb]) return ;
17    if(!flag&&aa[lena]==cc[lenc]){
18        mat[lena][lenb]=1;
19          dfs(lena+1,lenb,lenc+1);
20    }
21    if(!flag&&bb[lenb]==cc[lenc]){
22        mat[lena][lenb]=1;
23       dfs(lena,lenb+1,lenc+1);
24    }
25 }
26 void input(int n,int a[])
27 {
28     for(int i=1;i<=n;i++)
29        scanf("%d",&a[i]);
30 }
31 int main()
32 {
33     #ifdef LOCAL
34     freopen("test.in","r",stdin);
35     #endif
36     while(scanf("%d%d",&n1,&n2)&&n1+n2!=0)
37     {
38         input(n1,aa);
39         aa[n1+1]=-1;
40         input(n2,bb);
41         bb[n2+1]=-1;
42         input(n1+n2,cc);
43         flag=0;
44         memset(mat,0,sizeof(mat));
45         dfs(1,1,1);
46         if(flag)printf("possible\n");
47         else printf("not possible\n");
48     }
49  return 0;
50 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

HDU 4597 Play Game(DFS,区间DP)

Play Game Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K ...

31050
来自专栏ml

hdu----(1599)最大子矩阵(几何/dp)

最大子矩阵 Time Limit: 30000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (J...

29740
来自专栏小樱的经验随笔

HDU 2561 第二小整数

第二小整数 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

34980
来自专栏算法修养

HDU 5675 ztr loves math

ztr loves math Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65...

41360
来自专栏HansBug's Lab

3212: Pku3468 A Simple Problem with Integers

3212: Pku3468 A Simple Problem with Integers Time Limit: 1 Sec  Memory Limit: 12...

33680
来自专栏ml

POJ--Strange Way to Express Integers

Strange Way to Express Integers Time Limit: 1000MS Memory Limit: 131072K ...

28370
来自专栏算法修养

CodeForces 25C(Floyed 最短路)

F - Roads in Berland Time Limit:2000MS     Memory Limit:262144KB     64bit IO...

24640
来自专栏ml

hust--------The Minimum Length (最短循环节)(kmp)

F - The Minimum Length Time Limit:1000MS     Memory Limit:131072KB     64bit I...

31030
来自专栏HansBug's Lab

1648: [Usaco2006 Dec]Cow Picnic 奶牛野餐

1648: [Usaco2006 Dec]Cow Picnic 奶牛野餐 Time Limit: 5 Sec  Memory Limit: 64 MB Subm...

34970
来自专栏小樱的经验随笔

HDU 1012 u Calculate e【暴力打表,水】

u Calculate e Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3276...

28430

扫码关注云+社区

领取腾讯云代金券