全都是普及+的傻逼dp题，但是自己dp能力实在太弱，就都去写了一下。。。

下面是一些稍微没有那么傻逼的题，然后自己对dp的一些思考就放在了这里（我dp真的刚入门）

F

Description

求两个串的LCS并输出方案

n≤3000n\le 3000

Solution

以前没仔细想过如何输出方案，于是调了半天才过。。。

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
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

inline void proc_status()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
}

template <typename T> T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int Maxn = 3000 + 100;

int N, M, Dp[Maxn][Maxn];
char S[Maxn], T[Maxn];

stack <char> Stack;

inline void Solve ()
{
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
		{
			Dp[i][j] = max(Dp[i - 1][j], Dp[i][j - 1]);
			if (S[i] == T[j]) Chkmax(Dp[i][j], Dp[i - 1][j - 1] + 1);
		}
	int tmp = Dp[N][M];
	for (int i = N; i >= 1; --i)
		for (int j = M; j >= 1; --j)
		{
			if (S[i] == T[j] && Dp[i][j] == tmp)
			{
				--tmp, Stack.push(S[i]);
				break;
			}
		}
	while (!Stack.empty()) printf("%c", Stack.top()), Stack.pop();
}

inline void Input ()
{
	scanf("%s", S + 1); scanf("%s", T + 1);
	N = strlen(S + 1), M = strlen(T + 1);
}

int main()
{
#ifdef hk_cnyali
	freopen("F.in", "r", stdin);
	freopen("F.out", "w", stdout);
#endif
	Input();
	Solve();
	return 0;
}

J

Description

有nn个盘子，第ii个盘子里有ai(1≤ai≤3)a_i(1\le a_i\le 3)个寿司，重复以下操作直至所有寿司都被拿完：

  • 等概率选择一个盘子，如果盘子里有寿司则吃掉一个，否则什么也不做

问吃掉所有寿司的期望操作次数

n≤300n\le 300

Solution

dp时记录当前还剩一个、两个、三个的盘子分别有多少，记搜即可

1
2
3
4
5
6
7
8
9
10
11
inline double Calc (int i, int j, int k)
{
	if (Dp[i][j][k]) return Dp[i][j][k];
	if (i + j + k == 0) return 0;
	double ans = 1;
	if (i) ans += Calc(i - 1, j, k) * i / N;
	if (j) ans += Calc(i + 1, j - 1, k) * j / N;
	if (k) ans += Calc(i, j + 1, k - 1) * k / N;
	if (i + j + k != N) ans *= 1.0 * N / (1.0 * i + j + k);
	return Dp[i][j][k] = ans;
}

K

简单博弈题，懒得放题意了

对于一个局面，只要它能够走到必败态它就是必胜态

暴力做法的话在转移的时候要先拓扑排序处理一下

L

也懒得放题意了，区间dp模板题

我的暴力做法调了大半天，转移的细节需要稍微注意一下

O

Description

给一张每边nn个点的二分图，求完美匹配数量

n≤21n\le 21

Solution

表示左边前 个人匹配右边 状态的方案数，直接转移

R

Description

求一个nn个点的有向图长度为kk的不同路径数量对109+710^9+7取模

n≤50,k≤1018n\le50, k\le 10^{18}

Solution

矩阵快速幂优化

S

数位dp模板题

以前没怎么写过数位dp，它的套路是在记搜的时候记录一下当前有没有卡在上界，以此决定后面能填的最高为是多少

1
2
3
4
5
6
7
8
9
10
11
12
inline int get_dp (int x, int sum, int limit)
{
	if (!limit && Vis[x][sum]) return Dp[x][sum];
	if (x == N + 1) { if (!sum) return 1; return 0; }

	int Max = limit ? A[x] : 9, ans = 0;
	for (int i = 0; i <= Max; ++i)
		Add (ans, get_dp (x + 1, (sum + i) % D, limit && i == Max));

	if (!limit) Dp[x][sum] = ans, Vis[x][sum] = 1;
	return ans;
}

T

经典套路，和地精部落类似

U

枚举子集/超集技巧：

1
2
for (int sub = state; sub; sub = (sub - 1) & state)
for (int super = state; super <= ALL; super = (super + 1) | state)

V

直接dp，在从父亲向儿子转移时因为模数不是质数不能除，所以要记录前后缀积转移

W

Description

有mm个区间[li,ri][l_i, r_i]，每个价值为aia_i

对于一个长度为nn的01串，如果1在[li,ri][l_i, r_i]中至少出现一次，则区间会对答案产生aia_i的贡献

求所有01串中答案的最大值

Solution

考虑一个区间，我们只在它里面最右边那个1的位置计算它的贡献，这样就避免了会重复计算答案的问题

设dp[i]dp[i]位为1时，前ii位的最大价值和

dp[i]=maxj<idp[j]dp[i] = \max_{j < i}dp[j]

对于一个区间，我们在经过它右端点的时候再让[li,ri][l_i, r_i]的dp值加上aia_i，用线段树维护即可

Code

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
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
}

const int Maxn = 2e5 + 100;

int N, M;
struct info
{
	int l, r, w;
} A[Maxn];

inline int cmp (info a, info b) { return a.r < b.r; }

namespace SEG
{
#define mid ((l + r) >> 1)
#define ls node[root << 1]
#define rs node[root << 1 | 1]
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
	struct tree
	{
		LL max, tag;
	}node[Maxn << 2];

	inline void push_up (int root) { node[root].max = max(ls.max, rs.max); }

	inline void push_down (int root, int l, int r)
	{
		if (!node[root].tag) return ;
		ls.tag += node[root].tag; ls.max += node[root].tag;
		rs.tag += node[root].tag; rs.max += node[root].tag;
		node[root].tag = 0;
	}

	inline void update (int root, int l, int r, int x, int y, LL z)
	{
		if (x <= l && r <= y) node[root].max += z, node[root].tag += z;
		else
		{
			push_down(root, l, r);
			if (x <= mid) update (lson, x, y, z);
			if (y > mid) update (rson, x, y, z);
			push_up (root);
		}
	}

	inline LL query (int root, int l, int r, int x, int y)
	{
		if (x <= l && r <= y) return node[root].max;
		else
		{
			push_down(root, l, r);
			LL ans = 0;
			if (x <= mid) ans = max(ans, query (lson, x, y));
			if (y > mid) ans = max(ans, query (rson, x, y));
			return ans;
		}
	}

#undef mid
#undef ls
#undef rs
#undef lson
#undef rson
}

inline void Solve ()
{
	sort(A + 1, A + M + 1, cmp);
	
	int j = 1;
	for (int i = 1; i <= N; ++i)
	{
		SEG :: update (1, 1, N, i, i, SEG :: query (1, 1, N, 1, i));

		while (A[j].r == i)
		{
			SEG :: update (1, 1, N, A[j].l, A[j].r, A[j].w);
			++j;
		}
	}

	cout<<max(0ll, SEG :: node[1].max)<<endl;
}

inline void Input ()
{
	N = read<int>(), M = read<int>();
	for (int i = 1; i <= M; ++i)
		A[i].l = read<int>(), A[i].r = read<int>(), A[i].w = read<int>();
}

int main()
{
#ifdef hk_cnyali
	freopen("W.in", "r", stdin);
	freopen("W.out", "w", stdout);
#endif
	Input();
	Solve();
	return 0;
}

X

贪心地考虑，对于两个物品ii、jj而言，ii如果在jj前面被选，那么把ii放jj前面所剩的空间要比把jj放ii前面所剩的空间多，即sj−vi>si−vjs_j - v_i > s_i - v_j，即si+vi<sj+vjs_i + v_i < s_j + v_j

按这个排序后直接dp即可

Y

Description

一个H×WH\times W的网格，上面有nn个关键点，问从(1,1)(1,1)走到(H,W)(H, W)且不经过这nn个点的方案数S（只能向下或向右走），答案对109+710^9+7取模

Solution

不难想到最简单的容斥，设dp[i]dp[i]表示从(1,1)(1,1)走到xi,yix_i, y_i且中途不经过关键点的方案数

那么dp[i]=(xi+yi−2xi−1)∑xj<xi,yj<yi(xi−xj+yi−yjxi−xj)⋅dp[j]dp[i] = \binom{x_i+y_i-2}{x_i-1}\sum_{x_j < x_i, y_j < y_i}\binom{x_i-x_j+y_i-y_j}{x_i-x_j}\cdot dp[j]

排个序就没了

Z

斜率优化模板题，另外写一篇文章总结一下