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
  
   
#include
   
     #include 
    
      #include 
     
       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; }