题解：P9743 「KDOI-06-J」旅行

naughty-naught / 2024-10-15 / 原文

Problem Link

「KDOI-06-J」旅行

题意

题目讲的很清楚，不再过多赘述。

Solution

不难想到 $O(n^2 \times m^2 \times k)$ 的做法：定义 $f_{i,j,val,x,y}$ 为当前在 $(x, y)$ 的位置，花费 $val$ 元，手上有 $x$ 张 $L$ 公司的票，$y$ 张 $Z$ 公司的票的方案数，至于空间问题，滚动数组滚掉第一维即可。

转移分 $5$ 类讨论，其他疑问见代码。

Code

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

typedef long long ll;
#define Maxn 50
#define Maxk 95
#define Mod 998244353
#define fo(i, l, r) for (int i = l; i <= r; ++i)
#define fr(i, r, l) for (int i = l; i >= r; --i)
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21], *p1 = buf, *p2 = buf;
inline int read(int x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}

int n, m, k, a[Maxn][Maxn], b[Maxn][Maxn];
ll f[2][Maxn][Maxk][Maxn][Maxn], ans[Maxn][Maxn];

int main()
{
    n = read(), m = read(), k = read();
    fo(i, 1, n) fo(j, 1, m) a[i][j] = read();
    fo(i, 1, n) fo(j, 1, m) b[i][j] = read();
    f[1][1][0][0][0] = 1; // 初始状态
    fo(i, 1, n) fo(j, 1, m)
    {
        int t = i&1; if(i-1) f[t][j][0][0][0] = 0;
        fo(val, 1, k) fo(x, 0, n-i) fo(y, 0, m-j)
        {
            ll tmp = 0;
            if(x && val >= a[i][j]) (tmp += f[t][j][val - a[i][j]][x-1][y]) %= Mod;
            if(y && val >= b[i][j]) (tmp += f[t][j][val - b[i][j]][x][y-1]) %= Mod;
            if(x && y && val >= a[i][j]+b[i][j]) ((tmp -= f[t][j][val-a[i][j]-b[i][j]][x-1][y-1]) += Mod) %= Mod;
            if(i-1) (tmp += f[t^1][j][val][x+1][y]) %= Mod;
            if(j-1) (tmp += f[t][j-1][val][x][y+1]) %= Mod;
            f[t][j][val][x][y] = tmp; // 记忆化
            if(val == k && !x && !y) ans[i][j] = tmp; //是答案
        }
    }
    fo(i, 1, n)
    {
        fo(j, 1, m) printf("%lld ", ans[i][j]);
        puts("");
    }
    return 0;
}