每日一题：队列之和

题目

给你两个队列$a$和$b$，问你能否构造出给定的队列$c$。

Solutuon

很经典的动态规划，$dp[i][j]$ 表示第一个队列的前 $i$ 个数和第二个队列的第 $j$ 个数能否组成第三个队列的前 $i+j$ 个数。状态转移方程：$dp[i][j] = (dp[i - 1][j]$ $and$ $a[i] == c[i + j]$ $or$ $dp[i][j - 1]$ $and$ $b[j] == c[i + j])$。

Code

#include <bits/stdc++.h>
using namespace std;

int dp[1005][1005], T, A, B, a[1005], b[1005], c[2005];

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &A, &B);
    for (int i = 1; i <= A; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= B; i++) scanf("%d", &b[i]);
    for (int i = 1; i <= A + B; i++) scanf("%d", &c[i]);
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int t = 1; t <= A + B; t++) {
      for (int i = 0; i <= A; i++) {
        int j = t - i;
        if (j < 0 || j > B) continue;
        if (i && c[t] == a[i] && dp[i - 1][j]) dp[i][j] = 1;
        if (j && c[t] == b[j] && dp[i][j - 1]) dp[i][j] = 1;
      }
    }
    if (dp[A][B])
      puts("possible");
    else
      puts("not possible");
  }
  return 0;
}