B – Maja

考虑超级暴力，设计状态\(dp[k][i][j]\)为走了\(k\)步处于\((i, j)\)的答案：

\[ dp[k][i][j] = mp[i][j] + \max \begin{cases} dp[k – 1][i – 1][j] \\ dp[k – 1][i + 1][j] \\ dp[k – 1][i][j + 1] \\ dp[k – 1][i][j – 1] \end{cases} \]

而事实上，有一个显然的事实：通常最有路径都是走到一个特定的点，并在剩余的步数中会在两个格子之间重复走过，这样的平均值会更高（自行思考）。所以，\(k\)的维度只需要开到\(\min(\frac{k}{2}, nm)\)就行了，然后与此同时进行答案更新即可。

// B.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 110;

ll n, m, mp[MAX_N][MAX_N], a, b, k, dp[2][MAX_N][MAX_N];

int main()
{
	freopen("maja.in", "r", stdin);
	freopen("maja.out", "w", stdout);
    scanf("%lld%lld%lld%lld%lld", &n, &m, &a, &b, &k);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%lld", &mp[i][j]);
    ll gans = 0;
    memset(dp[0], -1, sizeof(dp[0]));
    dp[0][a][b] = 0;
    for (int w = 1; w <= min(n * m, k >> 1); w++)
    {
        memset(dp[w & 1], -1, sizeof(dp[w & 1]));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                ll best = max(dp[(w - 1) & 1][i - 1][j], max(dp[(w - 1) & 1][i + 1][j], max(dp[(w - 1) & 1][i][j - 1], dp[(w - 1) & 1][i][j + 1])));
                if (best == -1)
                    continue;
                dp[w & 1][i][j] = mp[i][j] + best;
                // w steps;
                // to bet it;
                if ((k - 2 * w) & 1)
                    continue;
                best = max(mp[i - 1][j], max(mp[i + 1][j], max(mp[i][j + 1], mp[i][j - 1])));
                gans = max(gans, dp[w & 1][i][j] * 2 + ((k - 2 * w) >> 1) * (mp[i][j] + best) - mp[i][j]);
            }
    }
    printf("%lld", gans);
    return 0;
}

C – djq的朋友圈

这道题挺妙的。

首先 70 分的状压 DP 是很好想的，状压时会自动搞定状态顺序的问题。考虑 100 分满分做法，发现直连点和间接连接点分成两类之后，总有一类的数量小于 20。所以这样，状态就压得下来了。

// C.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 55, INF = 0x3f3f3f3f;

int mp[MAX_N][MAX_N], dp[(1 << 24)], n, m, ans;
int statA, statB, id[MAX_N];
ll con[MAX_N], dev[MAX_N];

int lowbit(int x) { return x & (-x); }

int main()
{
    memset(mp, -1, sizeof(mp)), memset(id, -1, sizeof(id));
    scanf("%d%d", &n, &m);
    for (int i = 1, tmpx, tmpy, tmpz; i <= m; i++)
        scanf("%d%d%d", &tmpx, &tmpy, &tmpz), mp[tmpx][tmpy] = mp[tmpy][tmpx] = tmpz;
    for (int i = 2; i <= n; i++)
        if (mp[1][i] != -1)
        {
            id[i] = ++statA, ans += (mp[1][i] ^ 1);
            for (int j = 2; j <= n; j++)
                if (mp[1][j] == -1 && mp[i][j] != -1)
                {
                    id[j] = (id[j] == -1) ? ++statB : id[j];
                    con[id[i]] |= 1LL << (id[j] - 1);
                    dev[id[i]] |= (1LL * (mp[1][i] ^ mp[i][j] ^ 1)) << (id[j] - 1);
                }
        }
    if (statA <= 20)
    {
        for (int i = 0; i < (1 << statA); i++)
            dp[i] = -INF;
        dp[0] = 0;
        for (int i = 0; i < (1 << statA); i++)
            if (dp[i] >= 0)
            {
                ll cur = 0;
                for (int j = 0; j < statA; j++)
                    if ((i >> j) & 1)
                        cur |= con[j + 1];
                for (int j = 0; j < statA; j++)
                    if (!((i >> j) & 1))
                    {
                        int nxt = i | (1 << j), num = dp[i] + __builtin_popcountll(dev[j + 1] & (~cur));
                        if (dp[nxt] < num)
                            dp[nxt] = num;
                    }
            }
        ans += dp[(1 << statA) - 1];
    }
    else
    {
        for (int i = 0; i < (1 << statB); i++)
            dp[i] = -INF;
        dp[0] = 0;
        for (int i = 0; i < (1 << statB); i++)
            if (dp[i] >= 0)
                for (int j = 0; j < statA; j++)
                    if ((i | con[j + 1]) != i)
                    {
                        int nxt = (i | con[j + 1]), num = dp[i] + __builtin_popcountll(dev[j + 1] & (~i));
                        dp[nxt] = max(dp[nxt], num);
                    }
        ans += dp[(1 << statB) - 1];
    }
    printf("%d", ans);

    return 0;
}