#|2020/4/22每日一练算法|算法每日一练|dp

2020/4/22 1.组合数学dp 传送门
定义一个数组为good，当且仅当它能够划分为若干个这样的子段（首元素等于区间长度-1 且首元素>0）。求给出序列(长度1e3)中有多少个这样的子序列%mod。
可能有点绕上一下样例。

输入 4 1 1 1 1 输出 7 包括任取两个，因为数组[1,1]中a[1]=区间长度-1=2-1=1 以及全选，因为1 1 1 1可以划分为两个数组[1,1]

很自然就想到在i处时可以再其后任取a[i]个（a[i]>0时），但是这只是单独一个的，很明显两个成立的子序列拼接起来依旧成立，在这里就想断了。
看了题解是一个dp。
dp[j]表示位置j到结尾成立的序列数，那么dp[i]=ΣC(j-i-1,a[i]-1)*(1+dp[j+1]),再加上dp[i+1]。即在位置i处到位置j处（确定首尾），再在区间中任取a[i]-1个，再拼接上dp[j+1]的答案，+1是因为可以不拼接。
这里组合数用的比较频繁，采取递推预处理的方式。上代码。

#include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int maxn = 1e3 + 5; const ll inf = 0x3f3f3f3f; const ll mod = 998244353; #define all(x) x.begin(), x.end() int n; ll a[maxn], dp[maxn], C[maxn][maxn]; int main() { for (int i = 0; i <= 1000; i++) C[i][0] = 1, C[i][1] = i, C[i][i] = 1; for (int i = 1; i <= 1000; i++) { for (int j = 1; j <= 1000; j++) { C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; } } scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%lld", a + i); for (int i = n - 1; i >= 0; --i) { dp[i] += dp[i + 1]; if (a[i] > 0) { for (int j = i + a[i]; j < n; ++j) { dp[i] += C[j - i - 1][a[i] - 1] * (dp[j + 1] + 1) % mod; dp[i] %= mod; } } } printf("%lld\n", dp[0]); return 0; }

2.字符串dp 传送门
题意就是两个字符串中选出k个不重叠的公共子串的最长长度和。

输入 9 12 4 bbaaababb abbbabbaaaba 输出 7

【#|2020/4/22每日一练】

文章图片

emmm，完全没有思路。dp思想属实不够。
题解是这样的dp,dp[i][j][k][0/1]表示s串到位置i，t串中到位置j时，已经有k个相同的子串，最后一位表示当前结尾是否为最后一个子串的结尾(用于判断能否接上)。有了这个定义应该就很容易转移了。
搬一下别人的题解吧，我就不打了。
别人的题解