区间 DP

Posted by

P1880 [NOI1995]石子合并
经典例题

[USACO16OPEN]248 G
模板

[USACO16OPEN]262144 P
上一题的优化
dp[i][j] = dp[i-1][dp[i-1][j]];
dp[i][j]表示合并到数字是i,左端点是j的右端点的值;
当前i的数据是由i-1合并而来的,那么当前数据i的左端点就是上一次i-1合并的右端点;

codeforces 1336 C. Kaavi and Magic Spell

题解

f(l,r)为用s的前r-l+1个字符拼出t_{l\dots r}的方案数;
边界情况:t_i = s_1,f(i,i) = 2
转移:枚举长度为len,左边端点为l,则r = l + len – 1.
– 当 s_{len}=t_l,f(l,r), f(l,r)可由f(l+1,r)转移而来
– 当 s_{len}=t_r,f(l,r), f(l,r)可由f(l,r-1)转移而来

最后答案是\sum_{i=|t|}^{|s|}f(1,i)

#include <bits/stdc++.h>

using namespace std;
const int MOD = 998244353;
string ss, tt, s, t;
int dp[3010][3010];

int main()
{
    ss = "0"; cin >> s; ss += s;
    tt = "0"; cin >> t; tt += t;
    //cout << ss <<endl; cout << tt <<endl;
    int m = tt.size() - 1, n = ss.size() - 1;
    for (int i = 1; i <= m; i ++) 
        dp[i][i] = (ss[1] == tt[i]) << 1;
    for (int i = m + 1; i <= n; i ++) dp[i][i] = 2;
    for (int i = 2, len = 2; i <= n; i ++, len ++)
    {
        for (int l = 1, r = len; r <= n; l ++, r ++)
        {
            if (l > m || ss[i] == tt[l])
                dp[l][r] = (dp[l][r] + dp[l+1][r]) % MOD;
            if (r > m || ss[i] == tt[r])
                dp[l][r] = (dp[l][r] + dp[l][r-1]) % MOD;
        }
    }
    int ans = 0;
    for (int i = m ; i <= n; i ++) ans = (ans + dp[1][i]) % MOD;
    printf("%d\n", ans);
    return 0;
}

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注