洛谷 P4580 [BJOI2014] 路径

传送门

分析

可以考虑 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\) 进行转移：

1. 若 \(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][1]\)，因为这时若 \(v\) 上的 \(0\) 作首位，后面就不能接数字；
   3. 若 \(v\) 结点上是运算符或前括号，则将 \(dp[v][j - 1][k][2]\) 加到 \(dp[i][j][k][1]\)，因为数字前面一定可以接这两者；
   4. 由于后括号之后不接数字，所以 \(v\) 上是后括号时不转移。

   注意，当 \(v\) 上是数字时，当前位的数字就不作为首位。当 \(v\) 上不是数字，则当前位的数字就必然作为首位。

2. 若 \(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\) 是运算符时不转移。

3. 若 \(i\) 上是前括号：

   1. 当且仅当 \(v\) 上是运算符或前括号时可以将 \(dp[v][j - 1][k - 1][2]\) 加过来，因为只有这两者后才可以接前括号。（没说乘号可以省就不能省（确信））

   注意，由于多了一个未匹配的前括号，所以第三维从 \(k - 1\) 转移。

4. 若 \(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\) 的情况就不会出现非法。