P4580 路径

forgotmyhandle · 2023-10-04 21:22:55 · 题解

传送门

分析

可以考虑 dp。先朴素地定义 dp[i][j] 表示当前在结点 i，已经走过了 j 个结点（含当前）的方案数。发现没法处理括号匹配，于是加一维 k 表示当前还剩 k 个前括号没有匹配。又发现没法处理前导 0。于是考虑再加一维表示当前的最后一位是什么状态。

发现如果要排除掉前导 0 的话，只需要知道将要转移到我的这个状态所在结点上的 0 是不是作为一个数字的开头出现的即可。于是最后一维就可以表示这个结点上的数字是否作为首位出现。当然还要考虑当前位不是数字的情况。

于是有最终的状态：dp[i][j][k][0/1/2] 表示当前在 i 这个结点，已经经过了 j 个结点（含当前），还剩 k 个前括号没有匹配。最后一维是 1 代表当前结点上的数字作为首位出现，是 0 代表不作为首位，是 2 代表这一位根本就不是数字。

接下来考虑转移（前方有大分讨，请注意）：

对于 dp[i][j][k][0/1/2]，我们枚举所有与 i 相邻的结点 v 进行转移：

若 i 结点上是数字：
1. 若 v 结点上是非 0 数字，则将 dp[v][j - 1][k][0] + dp[v][j - 1][k][1] 加到 dp[i][j][k][0]，因为这时我们不关心 v 上的数是否作为首位；
2. 若 v 结点上是 0，则将 dp[v][j - 1][k][0] 加到 dp[i][j][k][0]，因为这时若 v 上的 0 作首位，后面就不能接数字；
3. 若 v 结点上是运算符或前括号，则将 dp[v][j - 1][k][2] 加到 dp[i][j][k][1]，因为数字前面一定可以接这两者；
4. 由于后括号之后不接数字，所以 v 上是后括号时不转移。
注意，当 v 上是数字时，当前位的数字就不作为首位。当 v 上不是数字，则当前位的数字就必然作为首位。
若 i 结点上是运算符：
1. 若 v 上为数字，则将 dp[v][j - 1][k][0] + dp[v][j - 1][k][1] 加过来，因为运算符前一定可以接数字；
2. 若 v 是前括号，则当且仅当 i 上为减号时可以将 dp[v][j - 1][k][2] 加过来，因为这时减号作负号用，而其他运算符均没有该用法；
3. 若 v 是后括号，则将 dp[v][j - 1][k][2] 加过来，因为后括号后一定可以接运算符；
4. 由于任意两运算符不能相连，于是当 v 是运算符时不转移。
若 i 上是前括号：
1. 当且仅当 v 上是运算符或前括号时可以将 dp[v][j - 1][k - 1][2] 加过来，因为只有这两者后才可以接前括号。（没说乘号可以省就不能省（确信））
注意，由于多了一个未匹配的前括号，所以第三维从 k - 1 转移。
若 i 上是后括号：
1. 若 v 上是数字，则将 dp[v][j - 1][k + 1][0] + dp[v][j - 1][k + 1][1] 加过来；
2. 若 v 上是后括号，则将 dp[v][j - 1][k + 1][2] 加过来；
3. 由于运算符后不能直接加后括号，括号内又不能为空，于是 v 为运算符或前括号时不转移。
注意，由于这个后括号匹配了一个前括号，所以第三维从 k + 1 转移。

赋初值的时候注意，当且仅当这个结点上是数字或前括号或减号时才能有初值。

统计答案时注意，当且仅当最后一位是后括号或数字时才可以加入答案。

代码

#include <iostream>
#define int long long
using namespace std;
const int p = 1000000007;
int head[200005], nxt[400005], to[400005], ecnt;
void addE(int u, int v) { to[++ecnt] = v, nxt[ecnt] = head[u], head[u] = ecnt; }
int n, m, K;
int dp[25][35][35][3];
// currently at point i, has passed j vertices, have k front bracket left to match
// l = (0 : this digit is not the beginning, 1 : is beginning, 2 : not a digit)
bool issym(char x) { return (x == '+' || x == '-' || x == '*' || x == '/'); }
bool isbrc(char x) { return (x == '(' || x == ')'); }
inline void add(int& x, int y) { x = (x + y) % p; }
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> K;
    string str;
    cin >> str;
    str = ' ' + str;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        addE(u, v);
        addE(v, u);
    }
    for (int i = 1; i <= n; i++) {
        if (isdigit(str[i])) 
            dp[i][1][0][1] = 1;
        else if (str[i] == '(') 
            dp[i][1][1][2] = 1;
        else if (str[i] == '-') 
            dp[i][1][0][2] = 1;
    }
    for (int j = 2; j <= K; j++) {
        for (int i = 1; i <= n; i++) {
            for (int k = (str[i] == '('); k <= K; k++) {
                for (int l = head[i]; l; l = nxt[l]) {
                    int v = to[l];    
                    if (isdigit(str[i])) {
                        if (isdigit(str[v])) 
                            add(dp[i][j][k][0], dp[v][j - 1][k][0] + (str[v] == '0' ? 0 : dp[v][j - 1][k][1]));
                        else if (issym(str[v]) || str[v] == '(') 
                            add(dp[i][j][k][1], dp[v][j - 1][k][2]);
                    } else if (issym(str[i])) {
                        if (isdigit(str[v])) 
                            add(dp[i][j][k][2], dp[v][j - 1][k][0] + dp[v][j - 1][k][1]);
                        else if (str[v] == '(') 
                            str[i] == '-' ? add(dp[i][j][k][2], dp[v][j - 1][k][2]) : void();
                        else if (str[v] == ')') 
                            add(dp[i][j][k][2], dp[v][j - 1][k][2]);
                    } else if (str[i] == '(') {
                        if (issym(str[v]) || str[v] == '(') 
                            add(dp[i][j][k][2], dp[v][j - 1][k - 1][2]);
                    } else {
                        if (isdigit(str[v])) 
                            add(dp[i][j][k][2], dp[v][j - 1][k + 1][0] + dp[v][j - 1][k + 1][1]);
                        else if (str[v] == ')') 
                            add(dp[i][j][k][2], dp[v][j - 1][k + 1][2]);
                    }
                }

            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (isdigit(str[i])) 
            add(ans, dp[i][K][0][0] + dp[i][K][0][1]);
        else if (str[i] == ')')
            add(ans, dp[i][K][0][2]);
    }
    cout << ans;
    return 0;
}

关于什么情况下要赋初值：

这里的 dp 值的意义实际上是当前合法的方案数加上当前非法但到后面可能变得合法的方案数。显然只有一个减号或前括号都是可能变得合法的，于是有初值。又显然只有一个后括号或别的运算符都是永远也不可能变得合法的，于是就没有初值。

关于统计答案：

显然这里的非法情况只有两种；运算符缺第二个参数和前括号没匹配完。于是只要最后一位是数字或后括号，再加上只统计第三维是 0 的情况就不会出现非法。