P8273 DP

Usada_Pekora · 2022-06-06 15:02:35 · 题解

看到数据范围再考虑到 USACO 从不卡常，可以猜想这应该是个 O(N^2) 的 DP。

首先对输入串做一个处理：如果有乘 0 的操作，那前面就没用了，如果有乘 1 的操作，对答案没有影响，直接舍去。

小学数学里有乘法交换律和加法交换律： a\cdot b = b \cdot a,a + b = b + a ，也就是说，如果两个同类操作放在一起，那么交换它们产生的结果不变。

定义一种对 (x,y) ， 其中 x 是来自 A 的操作， y 是来自 B 的操作，且操作类型相同。

那么答案是不包含这类对 (x,y) 的串的数量，因为出现这种情况的时候把 x,y 交换，直到没有这种对后，表达式的结果不变。

设 f[i][j][0/1] 表示 A 串匹配到 i 位，B 串匹配到 j 位，最后一个是 A 或者 B 的指令的答案。

对于结尾为 0 的情况： f[i+1][j][0] = f[i][j][0]+f[i][j][1] ：因为这些串都合法，所以在后面插入一个新的来自 A 的操作的新串不会不合法。

对于结尾为 1 的情况 ： 如果是 A_i \neq B_{j+1} ，则 f[i][j+1][1]=f[i][j][0]+f[i][j][1] ，否则 f[i][j+1][1]=f[i][j][1] 。

边界条件： f[0][0][1] = 1 ，虽然没有具体意义，但只有最后一维是 1 才能合法的开始转移，或者手推也行（只不过我比较懒）。

UPDATE ：去了 memset 以后，跑的飞快，一发卡进最优解。

#include <bits/stdc++.h>
using namespace std;
const int N = 2005, mod = 1e9 + 7;
int n, f[N][N][2], lena, lenb, T;
char str[N], a[N], b[N];
inline void read(char s[], int &slen) {
    slen = 0;
    cin >> str;
    int len = strlen(str);
    for(int i = 0; i < len; i++) {
        if(str[i] == '0') slen = 0;
        else if(str[i] == '1') continue;
        if(str[i] != '+') str[i] = '*';
        s[++slen] = str[i];
    }
}
inline int add(int a, int b) {
    a += b;
    return a >= mod ? a - mod : a;
}
signed main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while(T--) {
        cin >> n;
        read(a, lena), read(b, lenb);
        f[0][0][1] = 1;
        for(int i = 0; i <= lena; i++) {
            for(int j = 0; j <= lenb; j++) {
                if(i < lena) f[i + 1][j][0] = add(f[i][j][0], f[i][j][1]);
                if(j < lenb) f[i][j + 1][1] = f[i][j][1];
                if(i > 0 && j < lenb && a[i] != b[j + 1]) f[i][j + 1][1] = add(f[i][j + 1][1], f[i][j][0]);
            }
        }
        printf("%d\n", add(f[lena][lenb][0], f[lena][lenb][1]));
    }
    return 0;
}