百度春招算法岗笔试，编程DP题(27%+36%)，惨不忍睹。

两道题通过率分别是：27% + 36%，惨不忍睹啊。。

1. 分别给两行正整数和，数组 A 和 B 的长度都是 n，一共有 m 个回合，每回合从数组 A 中取出一个数字，然后数组 A 的剩下每个数字都减去变成，问个回合后所有取出数字和最大是？数据范围, , 。

想法：只通过 27% 先把所有输入按照 B 数组从大到小排序，令表示从前个数字中，经过回合可以取出的最大数字和。则：

时间复杂度：。交上去报 RE 错误。。。搞不懂了。。。

另外一种（错误的）贪心的思路是每次取剩下所有数字中的最大值，通过率也是 27%。。。。。

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const int N = 1100;

int n, m;
int A[N], B[N], dp[N][N], vis[N];

int greedy() {
    memset(vis, 0, sizeof(vis));
    int ans = 0;
    for (int i = 0; i < m; ++i) {
        int find = -1, Max = -0x3f3f3f3f;
        for (int j = 0; j < n; ++j) if (!vis[j]) {
            if (A[j] > Max) {
                Max = A[j];
                find = j;
            }
        }
        ans += A[find];
        vis[find] = 1;
        for (int j = 0; j < n; ++j) if (!vis[j]) A[j] -= B[j];
    }
    return ans;
}

struct Point {
    int a, b;

    bool operator < (const Point& rhs) const {
        return b > rhs.b ? true : a >= rhs.a;
    }
} pt[N];

int solve() {
    for (int i = 0; i < n; ++i) {
        pt[i].a = A[i];
        pt[i].b = B[i];
    }
    sort(pt, pt + n);

    int Max = -inf;
    for (int i = 0; i < n; ++i) {
        for (int k = 0; k <= m; ++k) dp[i][k] = -inf;
        dp[i][0] = 0;
        Max = max(Max, pt[i].a);
        dp[i][1] = Max;
    }

    for (int k = 2; k <= m; ++k) {
        for (int i = k-1; i < n; ++i) {
            dp[i][k] = max(dp[i-1][k], dp[i-1][k-1] + pt[i].a - (k-1) * pt[i].b);
        }
    }
    return dp[n-1][m];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> A[i];
    for (int i = 0; i < n; ++i) cin >> B[i];

    cout << solve() << endl;
    // cout << greedy() << endl;
    return 0;
}

2. 长度为的合法括号序列，给每个括号染色，规则是：

• 每个括号和其对应的括号，其中一个必须是红色，另一个是绿色或者蓝色
• 相邻的两个括号颜色不能相同

求所有染色方案数。对 998244353 取模。

想法：只通过 36%

区间 DP。令表示处理完区间且 l 位置染色为 i，r 位置染色为 j 的方案数，其中， 0， 1 和 2 分别表示红色，绿色和蓝色。对于每个位置的括号，记录其对应括号的位置为。

考虑更新，分两种

• 如果, 则由更新
• 如果，则由和更新得到。

更新时枚举每个区间端点的颜色。

时间复杂度：。

#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const ll mod = 998244353;
const int N = 510;

int n;
string s;
int match[N];
ll dp[N][N][3][3];

inline void add(ll& x, ll y) {
    x = (x + y % mod) % mod;
}

void solve(int l, int r) {
    if (l + 1 == r) {
        dp[l][r][0][1] = dp[l][r][0][2] = 1;
        dp[l][r][1][0] = dp[l][r][2][0] = 1;
        return;
    } else if (l > r) return;

    solve(l+1, match[l+1]);
    if (match[l+1] + 1 == r) {
        for (int i1 = 0; i1 < 3; ++i1) {
            for (int j1 = 0; j1 < 3; ++j1) if (i1 == 0 || j1 == 0) {
                if (i1 == 0 && j1 == 0) continue;
                for (int i2 = 0; i2 < 3; ++i2) {
                    for (int j2 = 0; j2 < 3; ++j2) if (i2 == 0 || j2 == 0) {
                        if (i2 == 0 && j2 == 0) continue;
                        if (i1 != 0 && i1 == i2) continue;
                        if (j1 != 0 && j1 == j2) continue;
                        add(dp[l][r][i1][j1], dp[l+1][r-1][i2][j2]);
                    }
                }
            }
        }
    } else {
        int p = match[l+1] + 1;
        solve(p, r-1);
        for (int i1 = 0; i1 < 3; ++i1) {
            for (int j1 = 0; j1 < 3; ++j1) if (i1 == 0 || j1 == 0) {
                if (i1 == 0 && j1 == 0) continue;
                for (int i2 = 0; i2 < 3; ++i2) {
                    for (int j2 = 0; j2 < 3; ++j2) if (i2 == 0 || j2 == 0) {
                        if (i2 == 0 && j2 == 0) continue;
                        for (int i3 = 0; i3 < 3; ++i3) {
                            for (int j3 = 0; j3 < 3; ++j3) if (i3 == 0 || j3 == 0) {
                                if (i3 == 0 && j3 == 0) continue;
                                if (i1 != 0 && i1 == i2) continue;
                                if (j2 != 0 && j2 == i3) continue;
                                if (j3 != 0 && j3 == j1) continue;
                                add(dp[l][r][i1][j1], 1LL * dp[l+1][p-1][i2][j2] * dp[p][r-1][i3][j3] % mod);
                            }
                        }
                    }
                }
            }
        }
    }
}

int main() {
    IOS; cin >> n >> s;
    stack<int> sta;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '(') sta.push(i);
        else {
            int t = sta.top(); sta.pop();
            match[i] = t; match[t] = i;
        }
    }
    solve(0, n-1);
    ll ans = 0;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) add(ans, dp[0][n-1][i][j]);
    }
    cout << ans << endl;
    return 0;
}