D、牛牛的01限定串

简单动态规划
如果你学过这个或者见过这个模型的动态规划那么这题就是个很简单很简单的dp。
）当然我不会，看了题解补提才马后炮的。
题解表示，这种两种状态的字符串，特别是给定的长度，每位个数是多少个的，转换到一个n + 1,m + 1的棋盘去看。
例如这题的第一个样例。
转化成一个 7 行 3列的棋盘， 下标从0开始。
先对模式S串处理，S串遇见一个0，我们把画笔向下画一格，S串遇见一个1，我们把画笔向右画一格。
这样我们走到 (i , j)这个位置的时候就能很清楚的知道有几个 0 和几个 1 。
那么在走的时候，再去赋值，棋盘把这些地方值改成对应的前缀值。
后缀值就是反着过来一遍，把这些地方改成后缀值。
那么问题就转换成了在一个赋有初值的地图上，从左上角走到右下角的问题。）这里因为越界问题，减少码量为前提，我选择从右下角走到左上角。
这就是最最最基础的动态规划了。注意两个dp数组的最大最小值初始化。

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e3 + 7;
const int INF = 0x3f3f3f3f;
char s[N], t[N];
int dp0[N][N], dp1[N][N];
int a[N][N]; //地图
int n, cnt0, cnt1, valpre, valsuf;

bool check(int x, int y) {
    if (x > cnt0 || x<0 || y>cnt1 || y < 0)    return false;
    return true;
}

int main() {
    n = read(), cnt0 = read(), cnt1 = read(), valpre = read(), valsuf = read();
    scanf("%s %s", s, t);
    int x = 0, y = 0; // 画笔x,y 0向下划，1向右划
    for (int i = 0; i < n; ++i) {
        if (s[i] == '0')    ++x;
        else    ++y;
        if (check(x, y))    a[x][y] = valpre;
    }
    x = cnt0, y = cnt1;
    for (int i = n - 1; ~i; --i) {
        if (s[i] == '0')    --x;
        else --y;
        if (check(x, y))    a[x][y] += valsuf;//记得这里累加不是赋值了
    }
    memset(dp0, 0x3f, sizeof(dp0));
    memset(dp1, -0x3f, sizeof(dp1));
    //dp0[0][0] = dp1[0][0] = a[0][0]; 从0开始后面好难特判，码量变大
    dp0[cnt0][cnt1] = dp1[cnt0][cnt1] = a[cnt0][cnt1];
    for (int i = cnt0; ~i; --i)
        for (int j = cnt1; ~j; --j) {
            if (t[i + j] == '0') {
                dp0[i][j] = min(dp0[i][j], dp0[i + 1][j] + a[i][j]); //越界是0+a[i][j]无所谓
                dp1[i][j] = max(dp1[i][j], dp1[i + 1][j] + a[i][j]);
            }
            if (t[i + j] == '1') {
                dp0[i][j] = min(dp0[i][j], dp0[i][j + 1] + a[i][j]);
                dp1[i][j] = max(dp1[i][j], dp1[i][j + 1] + a[i][j]);
            }
            if (t[i + j] == '?') {
                dp0[i][j] = min(dp0[i][j], dp0[i][j + 1] + a[i][j]); //康康从右边过来还是下面过来分数大
                dp1[i][j] = max(dp1[i][j], dp1[i][j + 1] + a[i][j]);
                dp0[i][j] = min(dp0[i][j], dp0[i + 1][j] + a[i][j]);
                dp1[i][j] = max(dp1[i][j], dp1[i + 1][j] + a[i][j]);
            }
        }
    printf("%d %d\n", dp0[0][0], dp1[0][0]);
    return 0;
}