前言：

这是笔者保证做过的且我自己认为很不错的$dp$题集，难度对应$codeforces$ $1800-2300$不等。点击题目有链接。

Fence Job（前缀和优化）

思路：

首先读完题可发现的是每个$h[i]$都有个极长区间，也就是$h[i]$只能在这个区间内出现，且作为该区间内的极小值。
看数据应该是$n^2$的$dp$,考虑从什么状态入手。我们发现不同的操作可能会出现相同的结果序列，那么我们从操作完最后的序列入手。$dp[i][j]$表示操作前$i$个数，且最后一个数以$a[j]$结尾的合法序列有多少种。考虑转移：如果最后一个数以$a[j]$结尾，那么前一个数只能以$x$结尾且$x\le a[j]$。
这么$dp[i][j]={\sum }_{x=1}^{j}dp[i-1][x],a[x]\le a[j]$.用前缀和优化转移即可。

code:

 	cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1; j <= n + 1; j++) 
            if(a[j] < a[i]) {
                r[i] = j;
                break;
            }
        for(int j = i - 1; j >= 0; j--) 
            if(a[j] < a[i]) {
                l[i] = j;
                break;
            }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(i == 1) {
                if(l[j] < i && i < r[j]) 
                    dp[i][j] = 1;
            } else {
                if(l[j] < i && i < r[j]) {
                    dp[i][j] += sum[i - 1][j];
                }
            }
            sum[i][j] = sum[i][j - 1] + dp[i][j];
        }
    }
    mint ans = 0;
    for(int i = 1; i <= n; i++) ans += dp[n][i];
    cout << ans << '\n';
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Yaroslav and Two Strings 线性dp

思路：

很裸的线性$dp$啊，发现状态无非就那么几个：
$f[i][0]:前i个数仅有s[j]\le w[j]$
$f[i][1]:前i个数有s[j]<w[j]\&\&s[j]>w[j]$
$f[i][2]:前i个数仅有w[j]\le s[j]$
$f[i][3]:前i个数仅有s[j]=w[j]$
暴力转移即可

code:

mint f[N][4];
signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
    auto now = clock();
#endif  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    string s, w;
    cin >> s >> w;
    s = ' ' + s; w = ' ' + w;
    f[0][3] = 1;
    for(int i = 1; i <= n; i++) {
        if(s[i] == '?' && w[i] == '?') {
            for(int x = 0; x <= 9; x++)
                for(int y = 0; y <= 9; y++) {
                    if(x < y) {
                        f[i][0] += f[i - 1][0] + f[i - 1][3];
                        f[i][1] += f[i - 1][1] + f[i-  1][2];
                    } else if(x > y) {
                        f[i][1] += f[i - 1][1] + f[i - 1][0];
                        f[i][2] += f[i - 1][2] + f[i - 1][3];
                    } else {
                        f[i][1] += f[i - 1][1];
                        f[i][2] += f[i - 1][2];
                        f[i][0] += f[i - 1][0];
                        f[i][3] += f[i - 1][3];
                    }
                }
        }
        if(s[i] != '?' && w[i] != '?') {
            int x = s[i] - '0', y = w[i] - '0';
            if(x > y) {
                f[i][0] = 0;
                f[i][1] = f[i - 1][1] + f[i - 1][0];
                f[i][2] = f[i - 1][2] + f[i - 1][3];
                f[i][3] = 0;
            } else if(x == y) {
                f[i][0] = f[i - 1][0];
                f[i][1] = f[i - 1][1];
                f[i][2] = f[i - 1][2];
                f[i][3] = f[i - 1][3];
            } else {
                f[i][0] = f[i - 1][0] + f[i - 1][3];
                f[i][1] = f[i - 1][1] + f[i - 1][2];
                f[i][2] = 0;
                f[i][3] = 0;
            }
        }
        if(s[i] != '?' && w[i] == '?') {
            int x = s[i] - '0';
            for(int y = 0; y <= 9; y++) {
                if(x > y) {
                    f[i][1] += f[i - 1][1] + f[i - 1][0];
                    f[i][2] += f[i - 1][2] + f[i - 1][3];
                } else if(x == y) {
                    f[i][0] += f[i - 1][0];
                    f[i][1] += f[i - 1][1];
                    f[i][2] += f[i - 1][2];
                    f[i][3] += f[i - 1][3];
                } else {
                    f[i][0] += f[i - 1][0] + f[i - 1][3];
                    f[i][1] += f[i - 1][1] + f[i - 1][2];
                }
            }
        }
        if(s[i] == '?' && w[i] != '?') {
            int y = w[i] - '0';
            for(int x = 0; x <= 9; x++) {
                if(x > y) {
                    f[i][1] += f[i - 1][1] + f[i - 1][0];
                    f[i][2] += f[i - 1][2] + f[i - 1][3];
                } else if(x == y) {
                    f[i][0] += f[i - 1][0];
                    f[i][1] += f[i - 1][1];
                    f[i][2] += f[i - 1][2];
                    f[i][3] += f[i - 1][3];
                } else {
                    f[i][0] += f[i - 1][0] + f[i - 1][3];
                    f[i][1] += f[i - 1][1] + f[i - 1][2];
                }
            }
        }
        if(s[i] != '?' && w[i] != '?') {
            int x = s[i] - '0', y = w[i] - '0';
            if(x > y) {
                f[i][1] = f[i - 1][1] + f[i - 1][0];
                f[i][2] = f[i - 1][2] + f[i - 1][3];
                f[i][3] = 0;
            } else if(x == y) {
                f[i][0] = f[i - 1][0];
                f[i][1] = f[i - 1][1];
                f[i][2] = f[i - 1][2];
                f[i][3] = f[i - 1][3];
            } else {
                f[i][0] = f[i - 1][0] + f[i - 1][3];
                f[i][1] = f[i - 1][1] + f[i - 1][2];
                f[i][2] = 0;
                f[i][3] = 0;
            }
        }
        // for(int j = 0; j < 4; j++) D(f[i][j])
    }
    cout << f[n][1];
#ifdef JANGYI
    cerr << "================================" << endl;
    cerr << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}   
/*
仅有：
f[i][0] : s[i] <= w[i];
f[i][1] : s[i] < w[i] & s[i] > w[i];
f[i][2] : s[i] >= w[i];
f[i][3] : s[i] == w[i];
 
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

杭电多校第三场[Two Permutations]（(https://acm.hdu.edu.cn/showproblem.php?pid=7173)（哈希或者记忆化搜索dp）

题意：

给定两个全排列数组$P,Q$,和一个空数组$R$,每次从两个数组的首位数字挑一个加到$R$后面，然后删除该数组。问：给定最后形成的$R$,求有多少种方案可以构成。

解法一：

我们会发现一个数字会出现两次，那么我们记录每个数字在$R$中第一次，第二次出现的位置。对于当前数字$p[i]$，枚举数字$p[i+1]$出现的位置，那么这两个位置中间就要放$Q$的一段，用哈希判断是否和$R$这一段子串完全匹配即可。

code:

typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int, int> pii;
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
} 
const int N = 3e5 + 10, M = N * 2, mod1 = 998244353, mod2 = 1e9 + 7;
inline LL ksm(LL a, LL b, int mod){
    LL ans = 1; 
    for(; b; b >>= 1, a = a * a % mod) if(b & 1) ans = ans * a % mod;
    return ans;
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};

//----------------------------------------------------------------------------------------//
ULL fb[N], fc[N << 1], p[N << 1];
int n, a[N], b[N], c[N << 1];
int dp[N][2], pos[N][2];

inline ULL get(ULL f[], int l, int r) {
    return f[r] - f[l - 1] * p[r - l + 1];
}
inline bool check(int lb, int rb, int lc, int rc) {
    if(lb > rb) return 1;
    if(lb < 1 || rb > n || lc < 1 || rc > n + n) return 0;
    return get(fb, lb, rb) == get(fc, lc, rc);
}
inline void up(int &x, int y) {
    x = x + y >= mod1 ? x + y - mod1 : x + y;
}
void solve() {
    read(n);
    for(int i = 1; i <= n; i++) read(a[i]);
    for(int i = 1; i <= n; i++) read(b[i]);
    for(int i = 1; i <= n + n; i++) read(c[i]);

    for(int i = 1; i <= n; i++) for(int j = 0; j < 2; j++) dp[i][j] = 0;
    for(int i = 1; i <= n; i++) pos[i][0] = pos[i][1] = 0;

    for(int i = 1; i <= n; i++) fb[i] = fb[i - 1] * 233 + b[i];
    for(int i = 1; i <= n << 1; i++) fc[i] = fc[i - 1] * 233 + c[i];
    for(int i = 1; i <= n << 1; i++) {
        if(!pos[c[i]][0]) pos[c[i]][0] = i;
        else pos[c[i]][1] = i;
    }
    int Q = 1;
    for(; Q <= n; Q++) if(!pos[Q][0] || !pos[Q][1]) break;
    if(Q != n + 1) {
        puts("0");
        return;
    }
    for(int j = 0; j < 2; j++) {
        int x = pos[a[1]][j];
        if(check(1, x - 1, 1, x - 1)) dp[1][j] = 1;
    }
    for(int i = 1; i < n; i++) {
        for(int j = 0; j < 2; j++) {
            if(dp[i][j]) {
                int x = pos[a[i]][j];
                for(int k = 0; k < 2; k++) {
                    int y = pos[a[i + 1]][k];
                    if(y <= x) continue;
                    if(check(x - i + 1, y - i - 1, x + 1, y - 1)) 
                        up(dp[i + 1][k], dp[i][j]);
                }
            }
        }
    }
    int ans = 0;
    for(int j = 0; j < 2; j++) 
        if(dp[n][j]) {
            int x = pos[a[n]][j];
            if(check(x - n + 1, n, x + 1, n + n )) up(ans, dp[n][j]);
        }
    printf("%d\n", ans);
}   
signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
    auto now = clock();
#endif
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    p[0] = 1;
    for(int i = 1; i < N << 1; i++) p[i] = p[i - 1] * 233;
    int T = 1;
    read(T);
    while(T--) {
        solve();
    }    

#ifdef JANGYI
    cout << "================================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}   

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

解法二：

我们定义$dp[i][0/1]$表示$R$的第$i$位与$P/Q$匹配的方案数。采用记忆化搜索的方法实现即可。

code：

int dp[2 * MAXN][2];

int dfs(int x, int y,int tar) {
    if (x > n && y > n)return 1;
    if (dp[x + y - 1][tar]!=-1)return dp[x + y - 1][tar];
    int ans = 0;
    if (P[x] == S[x + y - 1] && x <= n) {
        ans += dfs(x + 1, y, 0);
        ans %= mod;
    }
    if (Q[y] == S[x + y - 1] && y <= n) {
        ans += dfs(x, y + 1, 1);
        ans %= mod;
    }   
    return dp[x + y - 1][tar] = ans;
}

void slove() {
    cin >> n;
    for (int i = 0; i <= 2 * n + 5; i++)dp[i][0] = dp[i][1] = -1;
    for (int i = 1; i <= n; i++)cin >> P[i];
    for (int i = 1; i <= n; i++)cin >> Q[i];
    for (int i = 1; i <= 2 * n; i++)cin >> S[i];
    int ans = 0;
    if (P[1] == S[1])ans += dfs(2, 1, 0), ans %= mod;
    if (Q[1] == S[1])ans += dfs(1, 2, 1), ans %= mod;
    cout << ans << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

杭电多校第二场：E Slayers Come（线段树并查集优化）

题意：

给定一个长度为$n$的数组，每个位置有一个怪兽，有血量$b[i]$和攻击力$a[i]$。有$m$个技能，每个技能有三个参数：$V,L,R$：可以杀死$V$位置的怪物，这个怪物死后会攻击两边的怪，对左边造成$a[i]-L$伤害，右边造成$a[i]-R$的伤害。求如何组合技能使每个怪都被至少杀一次的方案。

思路：

首先可以发现每个技能是可以杀死一段区间内的怪物，那么我们如果能处理出来所有技能的区间$[L,R]$，那么问题就转化为从这些技能中选取若干使得区间$[1,n]$被覆盖，就是区间完全覆盖问题，看数据范围，很容易想到线段树优化，经典题啊！那么我们就该考虑如何快速求出每个技能的区间。依题意如果$a[i]-r[k]\ge b[i+1]$，那么我们就可以通过传递杀死它，那么我们把$a[i]-b[i+1]$按从大到小排序，把每个技能的$r$从小到大排序，优先处理容易死的怪，如果满足上述关系，那么就把$[i,i+1]$合并到一个连通块里，用并查集优化。左端点同理。
那么接下来解决如何组合技能是区间被重复覆盖。
对于当前区间$[L,R]$,
$dp[r]+={\sum }_{j=L-1}^{R}dp[j]$ ：选这个区间，那么左端点接在$[L-1,R]$的位置，都可以使$[1,R]$被覆盖。
$0\le j\le L-2,dp[j]=dp[j]\ast 2$：选不选这个区间，区间$[0,L-2]$还是会被覆盖，因为题目问的是如何组合技能。
优化用线段树即可。

code:

来自大佬的代码

#include 
#include 
#include 

using namespace std;
#define int long long
typedef pair<int, int> PII;
const int N = 2e5 + 10, mod = 998244353;
int n, m, a[N], b[N];
struct Node
{
    int v, l, r;
    int ll, rr;
}sk[N];
struct Tree
{
    int l, r;
    int sum;
    int tag;
}tr[N << 2];
int p[N];
PII d[N];

int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void pushup(int u)
{
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % mod;
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if(root.tag > 1)
    {
        left.sum = left.sum * root.tag % mod, right.sum = right.sum * root.tag % mod;
        left.tag = left.tag * root.tag % mod, right.tag = right.tag * root.tag % mod;
        root.tag = 1;
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 1};
    if(l == r) return ;
    else
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void add(int u, int x, int v)
{
    if(x == tr[u].l && x == tr[u].r) tr[u].sum = (tr[u].sum + v) % mod;
    else 
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) add(u << 1, x, v);
        if(x > mid) add(u << 1 | 1, x, v);
        pushup(u);
    }
}

void mul(int u, int l, int r)
{
    if(l <= tr[u].l && r >= tr[u].r) 
    {
        tr[u].sum = tr[u].sum * 2 % mod;
        tr[u].tag = tr[u].tag * 2 % mod;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) mul(u << 1, l, r);
        if(r > mid) mul(u << 1 | 1, l, r);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if(l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        int res = 0;
        if(l <= mid) res = (res + query(u << 1, l, r)) % mod;
        if(r > mid) res = (res + query(u << 1 | 1, l, r)) % mod;
        pushup(u);
        return res % mod;
    }
}

void solve()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++ ) cin >> a[i] >> b[i];
    for(int i = 1 ; i <= m ; i ++ )
    {
        int v, l, r;
        cin >> v >> l >> r;
        sk[i] = {v, l, r};
    }
    for(int i = 1 ; i <= n ; i ++ ) p[i] = i;
    for(int i = 1 ; i < n ; i ++ ) d[i] = {a[i] - b[i + 1], i};
    sort(d + 1, d + n);
    sort(sk + 1, sk + m + 1, [](Node &a, Node &b){
        return a.r > b.r;
    });
    int cur = n - 1;
    for(int i = 1 ; i <= m ; i ++ )
    {
        while(cur >= 1 && d[cur].first >= sk[i].r)
        {
            int pos = d[cur].second;
            p[pos] = pos + 1;
            cur -- ;
        }
        sk[i].rr = find(sk[i].v);
    }
        
    
    for(int i = 1 ; i <= n ; i ++ ) p[i] = i;
    for(int i = 1 ; i < n ; i ++ ) d[i] = {a[i + 1] - b[i] , i};
    sort(d + 1, d + n);
    sort(sk + 1, sk + m + 1, [](Node &a, Node &b){
        return a.l > b.l;
    });
    cur = n - 1;
    for(int i = 1 ; i <= m ; i ++ )
    {
        while(cur >= 1 && d[cur].first >= sk[i].l)
        {
            int pos = d[cur].second;
            p[pos + 1] = pos;
            cur --;
        }
        sk[i].ll = find(sk[i].v);
    }
    sort(sk + 1, sk + m + 1, [](Node &a, Node &b){
        return a.rr < b.rr;
    });

    build(1, 0, n);
    add(1, 0, 1);
    for(int i = 1 ; i <= m ; i ++ )
    {
        int l = sk[i].ll , r = sk[i].rr;
        add(1, r, query(1, l - 1, r));
        if(l >= 2) mul(1, 0, l - 2);
    }
    cout << query(1, n, n) << endl;
}

signed main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int T = 1;
    cin >> T;
    while(T -- ) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

Pawn（背包+记录路径）

思路：

首先$f[i][j][w]$表示从底部走到$(i,j)$且当前所有豆子总数$mod(k+1)=w$的最大豆子数。
那么转移我们就直接枚举是从下一层哪个方向走过来的即可，顺便记录一下路径。

code:

template<int m>
struct modint {
	unsigned int x;
	constexpr modint()noexcept:x(){}
	template<typename T>
	constexpr modint(T x_)noexcept:x((x_%=m)<0?x_+m:x_){}
	constexpr unsigned int val()const noexcept{return x;}
	constexpr modint&operator++()noexcept{if(++x==m)x=0;return*this;}
	constexpr modint&operator--()noexcept{if(x==0)x=m;--x;return*this;}
	constexpr modint operator++(int)noexcept{modint res=*this;++*this;return res;}
	constexpr modint operator--(int)noexcept{modint res=*this;--*this;return res;}
	constexpr modint&operator+=(const modint&a)noexcept{x+=a.x;if(x>=m)x-=m;return*this;}
	constexpr modint&operator-=(const modint&a)noexcept{if(x<a.x)x+=m;x-=a.x;return*this;}
	constexpr modint&operator*=(const modint&a)noexcept{x=(unsigned long long)x*a.x%m;return*this;}
	constexpr modint&operator/=(const modint&a)noexcept{return*this*=a.inv();}
	constexpr modint operator+()const noexcept{return*this;}
	constexpr modint operator-()const noexcept{return modint()-*this;}
	constexpr modint pow(long long n)const noexcept {
		if(n<0)return pow(-n).inv();
		modint x=*this,r=1;
		for(;n;x*=x,n>>=1)if(n&1)r*=x;
		return r;
	}
	constexpr modint inv()const noexcept {
		int s=x,t=m,x=1,u=0;
		while(t)
		{
			int k=s/t;
			s-=k*t;
			swap(s,t);
			x-=k*u;
			swap(x,u);
		}
		return modint(x);
	}
	friend constexpr modint operator+(const modint&a,const modint&b){return modint(a)+=b;}
	friend constexpr modint operator-(const modint&a,const modint&b){return modint(a)-=b;}
	friend constexpr modint operator*(const modint&a,const modint&b){return modint(a)*=b;}
	friend constexpr modint operator/(const modint&a,const modint&b){return modint(a)/=b;}
	friend constexpr bool operator==(const modint&a,const modint&b){return a.x==b.x;}
	friend constexpr bool operator!=(const modint&a,const modint&b){return a.x!=b.x;}
	friend ostream&operator<<(ostream&os,const modint&a){return os<<a.x;}
	friend istream&operator>>(istream&is,modint&a){long long v;is>>v;a=modint(v);return is;}
};
using mint = modint<1000000007>;
// using mint = modint<998244353>;
namespace Combine{
	const int Combine_max = 1e5 + 50;
	mint fac[Combine_max];
	void init() { fac[0] = 1; for (int i = 1; i < Combine_max; ++ i) fac[i] = fac[i - 1] * i; }
	mint A(int n, int m) { return fac[n] / fac[n - m]; }
	mint C(int n, int m) { return fac[n] / (fac[n - m] * fac[m]); }
	mint ksm(mint x, int exp){
		mint res = 1;
		for (; exp; x *= x, exp >>= 1) if (exp & 1) res *= x;
		return res;
	}
}
using namespace Combine;
 
int f[111][111][11]; //f[i][j][w]走到(i,j)，价值mod(k+1)=w的最大价值
int n, m, a[111][111];
pii road[111][111][11];
signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
    auto now = clock();
#endif  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k; 
    cin >> n >> m >> k;
    k++;
    memset(f, -1, sizeof f);
    for(int i = 1; i <= n; i++) {
        string s; cin >> s;
        for(int j = 1; j <= m; j++)
            a[i][j] = s[j - 1] - '0';
    }
    for(int i = n; i >= 1; i--) {
        for(int j = 1; j <= m; j++) {
            if(i == n) f[n][j][a[i][j] % k] = a[i][j];
            else {
                for(int w = 0; w < k; w++) { 
                    if(j > 1 && f[i + 1][j - 1][(w - a[i][j] % k + k) % k] != -1 && f[i + 1][j - 1][(w - a[i][j] % k + k) % k] + a[i][j] > f[i][j][w]) {
                        f[i][j][w] = f[i + 1][j - 1][(w - a[i][j] % k + k) % k] + a[i][j];
                        road[i][j][w] = {j - 1, (w - a[i][j] % k + k) % k};
                    } 
                    if(j < m && f[i + 1][j + 1][(w - a[i][j] % k + k) % k] != -1 && f[i + 1][j + 1][(w - a[i][j] % k + k) % k] + a[i][j] > f[i][j][w]) {
                        f[i][j][w] = f[i + 1][j + 1][(w - a[i][j] % k + k) % k] + a[i][j];
                        road[i][j][w] = {j + 1, (w - a[i][j] % k + k) % k};
                    }
                }
            }
        }
    }
    int ans = -1, id;
    for(int i = 1; i <= m; i++) {
        if(f[1][i][0] > ans) {
            ans = f[1][i][0];
            id = i;
        }
    }
    // D(id)
    if(ans == -1) {
        cout << -1 << '\n';
        return 0;
    }
    cout << ans << '\n';
    int i = 1, j = id, w = 0;
    vector<string> pos;
    while(i != n) {
        pii now = road[i][j][w];
        if(now.fi == j - 1) pos.pb("R");
        else pos.pb("L");
        // DD(i, j)
        i++;
        j = now.fi; w = now.se;
    }
    cout << j << '\n';
    reverse(all(pos));
    for(auto t : pos) cout << t;
#ifdef JANGYI
    cerr << "================================" << endl;
    cerr << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

[Slash] (https://ac.nowcoder.com/acm/contest/38457/E)（线性dp）

题意：

给一个字符矩阵和一个字符串$s$，每一次只能向右或向下走，问走过的路径上的字符连起来最多有多少个不相交的连续子串是$s$。比如：$abcdabc$中有两个$abc$。

思路：

朴素的线性$dp$,我们令$dp[i][j][k]$表示走到了$(i,j)$且当前已经最新匹配到$s$的第$k$个字符的最大数量。比如：$abcdeabc，s=abc$，那么$dp[1][3][0]=1，dp[1][6][1]=1,dp[1][8][0]=2$。那么其中是有一些不合法的状态，为了不让其影响我们正确状态的更新，我们把它们赋值成很小的数即可。那么我们应考虑如何转移$dp[i][j][0]$这个状态。$dp[i][j][0]$代表这个位置和$s$串失配了，那么它就可以由上一步的每个状态转移过来。

code:

string s, str[111];
int f[111][111][111];
signed main() {
#ifdef JANGYI
    freopen("input.in", "r", stdin);
    freopen("out.out", "w", stdout);
    auto now = clock();
#endif  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
	cin >> n >> m;
	cin >> s;
	int len = s.size();
	s = ' ' + s;
	for(int i = 1; i <= n; i++) cin >> str[i], str[i] = ' ' + str[i];
	memset(f, -0x3f, sizeof f);
	f[0][1][0] = 0;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			for(int k = 1; k <= len; k++) {
				if(str[i][j] == s[k]) 
					f[i][j][k] = max(f[i - 1][j][k - 1], f[i][j - 1][k - 1]);
			}
			f[i][j][0] = f[i][j][len] + 1;
			for(int k = 0; k <= len; k++)
				f[i][j][0] = max(f[i][j][0], max(f[i][j - 1][k], f[i - 1][j][k]));
		}
	}
	int ans = 0;
	for(int i = 0; i <= len; i++) ans = max(ans, f[n][m][i]);
	cout << ans << endl;
#ifdef JANGYI
    cerr << "================================" << endl;
    cerr << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38