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.

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.

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

题意非常明白。

很容易想到用回溯的办法从左到右枚举选择看能不能枚举到最右端。但是很明显，要超时！

这种每种选择有两种选择方式又包含大量重叠子问题的类型，适合用动规的思想。（想想 数字三角形 的问题）

但是想到用动规的思想，也不算解决问题。。。因为对于这道题目中的问题，你得定义适合的状态，想到正确有效的状态转移方程，给出边界条件才行。

状态定义：d[i][j]=1表示第一道上的前i辆和第二道上的前j辆车恰好是最终目标道上的前i+j辆车；

状态转移：if( a1[i] == a[i+j] ) d[i][j]=dp(i-1,j);

          if( a2[j] == a[i+j] ) d[i][j]=dp(i,j-1);

边界条件：好像这种布尔型一直延伸到最前端，所以不用特殊给出边界条件唉。。

我感觉这好像就是一个有向的动态规划，感觉像是线性的...

用记忆化搜索的方式。

其时间复杂度：总共最多可能有1000*1000个状态，其时间复杂度是O(n^2)；

实现：

#include<cstdio>
#include<cstring>
#include <cctype>
#include <iostream>
using namespace std;
int N1,N2,num1[1010],num2[1010],num[2010],N,d[1010][1010];
int dp(int a,int b)
{
    if(a<0 || b<0) return 0;
    int &ans=d[a][b];
    if(ans!=-1) return ans;
    ans=0;
    if(num1[a]==num[a+b]&&!ans) ans=dp(a-1,b);
    if(num2[b]==num[a+b]&&!ans) ans=dp(a,b-1);
    return ans;
}
int main()
{
    while(scanf("%d%d",&N1,&N2)==2 && N1 && N2)
    {
        N=N1+N2;
        memset(d,-1,sizeof(d));
        d[0][0]=1;
        for(int i=1;i<=N1;i++) scanf("%d",&num1[i]);
        for(int i=1;i<=N2;i++) scanf("%d",&num2[i]);
        for(int i=1;i<=N;i++) scanf("%d",&num[i]);
        if(dp(N1,N2)) printf("possible\n");
        else printf("not possible\n");
    }
    return 0;
}

hdu 3779 Railroad (动态规划)