striving & singing
$$(2i)^k=(-1)^{k/2}2^ki\ \ \ (k>0,k\bmod2=1)$$
$$(2i)^k=(-1)^{k/2}2^k\ \ \ (k\ge 0,k\bmod2=0)$$
$$(2i)^k=\dfrac{1}{(-1)^{-k/2}2^{-k}i}=-\dfrac{1}{(-1)^{-k/2}2^{-k}}i\ \ \ (k<0,k\bmod 2=1)$$
$$(2i)^k=\dfrac{1}{(-1)^{-k/2}2^{-k}}\ \ \ (k<0,k\bmod 2=0)$$
$$k+t+1$$
$$(2n+1)-(k+t+1)=2n-k-t$$
$$n-(2n-k-t)=k+t-n$$
$$\binom{k+t+1}{k+t-n}=\binom{k+t+1}{(k+t+1)-(k+t-n)}=\binom{k+t+1}{n+1}$$
$$\sum_{k=1}^n\binom{n-1}{k-1}\binom{n-1}{k-2}\binom{2k}{n+1}+2\binom{n-1}{k-1}\binom{n-1}{k-1}\binom{2k+1}{n+1}+\binom{n-1}{k-1}\binom{n-1}{k}\binom{2k+2}{n+1}$$
$$\sum_{k=1}^n\binom{n-1}{k-1}\left(\binom{n-1}{k-2}\binom{2k}{n+1}+2\binom{n-1}{k-1}\binom{2k+1}{n+1}+\binom{n-1}{k}\binom{2k+2}{n+1}\right)$$
https://www.luogu.com.cn/problem/P1006
从$(1,1)$到$(n,m)$，再从$(n,m)$到$(1,1)$的两条不相交路径，等价于从$(1,1)$到$(n,m)$的两条不相交路径。于是问题相当于矩形 DAG 图上的最长路问题中求一条最长路变成了求两条，且要求互不相交。受此启发可以设$dp[i][j][k][l]$表示两个点分别走到了$(i,j)$和$(k,l)$时的最长路。转移方程是显然的，因为比较长所以不写了。复杂度$O(n^4)$。
因为两个点是同步走的所以$i+j=k+l$，因此实际上刚刚设计的状态中有冗余信息。所以可以去掉一维，设$dp[s][i][k]$表示目前走了$s$步，一个走到了第$i$行，一个走到了第$k$行。$j$和$l$可以在转移时直接计算。那么有$dp[s][i][k]=\min(dp[s-1][i][k],dp[s-1][i-1][k],dp[s-1][i][k-1],dp[s-1][i-1][k-1])$。
同时还要满足路径不相交，可以令$i>j$，这样就可以保证路径不相交，因为显然一个在下面一个在上面。
刚开始我是设$dp[i][j][k]$表示一个点走到$(i,j)$，另一个点走到第$k$行时的最长路，这样做应该也是可以的，当时我以为这样不方便保证不相交，但现在看来这种状态和上面也是一样的道理，令$i>k$应该就可以了。
#include<cstdio>
int n, m, a[55][55], dp[110][55][55];
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
for (int s = 1; s <= n + m - 2; s++)
for (int i = 1; i <= s + 1 && i <= n; i++) {
int j = s - i + 2;
if (!(1 <= j && j <= m)) continue;
for (int k = 1; k < i; k++) {
int l = s - k + 2;
if (!(1 <= l && l <= m)) continue;
if (!(i - 1 == k - 1 && j == l)) dp[s][i][k] = max(dp[s][i][k], dp[s - 1][i - 1][k - 1] + a[i][j] + a[k][l]);
if (!(i - 1 == k && j == l - 1)) dp[s][i][k] = max(dp[s][i][k], dp[s - 1][i - 1][k] + a[i][j] + a[k][l]);
if (!(i == k - 1 && j - 1 == l)) dp[s][i][k] = max(dp[s][i][k], dp[s - 1][i][k - 1] + a[i][j] + a[k][l]);
if (!(i == k && j - 1 == l - 1)) dp[s][i][k] = max(dp[s][i][k], dp[s - 1][i][k] + a[i][j] + a[k][l]);
}
}
printf("%d\n", dp[n + m - 3][n][n - 1]);
return 0;
}https://www.luogu.com.cn/problem/P1541
以前做过，现在再做一遍练练手，毕竟很久没写 DP 了，真的是手生了，我现在都有点后悔当时计划不够科学。
设$dp[i][j][k][l]$表示四种卡片分别使用了多少张，然后直接转移即可。
#include<cstdio>
int n, m, a[400], dp[41][41][41][41], cnt[5];
inline int max(int a, int b) { return a > b ? a : b; }
inline int idx(int i, int j, int k, int l) { return i + j * 2 + k * 3 + l * 4 + 1; }
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) {
int x; scanf("%d", &x);
cnt[x]++;
}
dp[0][0][0][0] = a[1];
for (int i = 0; i <= cnt[1]; i++)
for (int j = 0; j <= cnt[2]; j++)
for (int k = 0; k <= cnt[3]; k++)
for (int l = 0; l <= cnt[4]; l++) {
if (i) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i - 1][j][k][l] + a[idx(i, j, k, l)]);
if (j) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j - 1][k][l] + a[idx(i, j, k, l)]);
if (k) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k - 1][l] + a[idx(i, j, k, l)]);
if (l) dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j][k][l - 1] + a[idx(i, j, k, l)]);
}
printf("%d\n", dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]]);
return 0;
}https://www.luogu.com.cn/problem/P1941
首先需要求能否完成游戏，那么设$dp[i][j]$表示从$(i,j)$出发能否完成游戏。那么有
$$dp[i][j]=(||_{k=j+a\times x[i],a\in N^{\ast}}dp[i+1][\min(k,m)])\ ||\ dp[i+1][\max(j-y[i],0)]$$
其中$||$表示逻辑或运算。这个转移起来是$O(m)$的，总复杂度$O(nm^2)$。可以用前缀和优化一下，取 presum 之意，设$ps[i][j]=||_{k=j+a\times x[i-1],a\in N}dp[i][\min(k,m)]$，那么现在方程变为：
$$dp[i][j]=ps[i+1][\min(j+x[i],m)]\ ||\ dp[i+1][\max(j-y[i],0)]$$
$$ps[i][j]=dp[i][j]\ ||\ ps[i][\min(j+x[i-1],m)]$$
另外，还需要判断$(i,j)$是否在柱子上，如果在柱子上那么显然$dp[i][j]=\text{false}$。两个都可以$O(1)$转移，那么现在总复杂度变成了$O(nm)$。然后还需要再 DP 一遍，计算最少需要跳几次，或者最多可以经过多少个柱子。
设$dp[i][j]$表示从$(i,j)$出发最少需要跳几次到终点，那么有：
$$dp[i][j]=\min(\min_{k=j+a\times x[i],a\in N^{\ast}}dp[i+1][\min(k,m)]+a,dp[i+1][\max(j-y[i],0)])$$
同理，上面这个方程也可以用前缀和优化：
$$dp[i][j]=\min(ps[i+1][\min(j+x[i],m)]+1,dp[i+1][\max(j-y[i],0)])$$
$$ps[i][j]=\min(dp[i][j],ps[i][\min(j+x[i-1],m)]+1)$$
类似地，如果$(i,j)$在柱子上那么$dp[i][j]=\inf$。
设$dp[i][j]$表示从$(i,j)$出发最多能过几根柱子，那么有：
$$dp[i][j]=\max(\max_{k=j+a\times x[i],a\in N^\ast}dp[i+1][\min(k,m)],dp[i+1][\max(j-y[i],0)])+\Delta$$
其中若第$j$列有柱子那么$\Delta=1$，否则$\Delta=0$。
上面这个方程也可以用前缀和优化：
$$dp[i][j]=\max(ps[i+1][\min(j+x[i],m)],dp[i+1][\max(j-y[i],0)])+\Delta$$
$$ps[i][j]=\min(dp[i][j],ps[i][\min(j+x[i-1],m)])$$
若$(i,j)$在柱子上，则$dp[i][j]=0$。
总复杂度$O(nm)$，做法很好理解，不过有点细节。
上面的是我自己推出来的做法，但其实我做完之后一看题解，发现如果把第一维压缩掉的话转移就直接变成了和完全背包、01 背包完全相同的形式，那么什么前缀和优化也不用了，直接 DP 即可，细节也少了亿点。
#include<cstdio>
#include<cstring>
int n, m, k, dp2[10010][1010], ps2[10010][1010], up[10010], down[10010], l[10010], h[10010], ans;
bool dp[10010][1010], ps[10010][1010], ok, vis[10010];
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < n; i++) scanf("%d%d", &up[i], &down[i]);
for (int i = 0; i < n; i++) h[i] = m + 1;
for (int i = 1; i <= k; i++) {
int p; scanf("%d", &p);
scanf("%d%d", &l[p], &h[p]); vis[p] = true;
}
for (int j = 1; j <= m; j++) {
dp[n][j] = true;
ps[n][j] = dp[n][j] || ps[n][min(j + up[n - 1], m)];
}
for (int i = n - 1; i >= 0; i--)
for (int j = m; j >= 1; j--) {
if (l[i] < j && j < h[i]) dp[i][j] = ps[i + 1][min(j + up[i], m)] || dp[i + 1][max(j - down[i], 0)];
if (i) ps[i][j] = dp[i][j] || ps[i][min(j + up[i - 1], m)];
}
for (int j = 1; j <= m; j++) ok = ok || dp[0][j];
if (ok) {
printf("1\n");
memset(dp2, 0x3f, sizeof dp2); memset(ps2, 0x3f, sizeof ps2);
for (int j = 1; j <= m; j++) dp2[n][j] = ps2[n][j] = 0;
for (int i = n - 1; i >= 0; i--)
for (int j = m; j >= 1; j--) {
if (l[i] < j && j < h[i]) dp2[i][j] = min(ps2[i + 1][min(j + up[i], m)] + 1, dp2[i + 1][max(j - down[i], 0)]);
if (i) ps2[i][j] = min(dp2[i][j], ps2[i][min(j + up[i - 1], m)] + 1);
}
ans = 0x3fffffff;
for (int j = 1; j <= m; j++) ans = min(ans, dp2[0][j]);
printf("%d\n", ans);
}
else {
printf("0\n");
for (int i = n - 1; i >= 0; i--)
for (int j = m; j >= 1; j--) {
if (l[i] < j && j < h[i]) {
if (vis[i]) dp2[i][j] = max(ps2[i + 1][min(j + up[i], m)], dp2[i + 1][max(j - down[i], 0)]) + 1;
else dp2[i][j] = max(ps2[i + 1][min(j + up[i], m)], dp2[i + 1][max(j - down[i], 0)]);
}
if (i) ps2[i][j] = max(dp2[i][j], ps2[i][min(j + up[i - 1], m)]);
}
for (int j = 1; j <= m; j++) ans = max(ans, dp2[0][j]);
printf("%d\n", ans);
}
return 0;
}https://www.luogu.com.cn/problem/P2340
如果已经确定其中一个属性的和为某个值，那么我们就可以直接贪心地让另一个属性之和最大。同时每个物品只能选择一次。这和 01 背包的形式相同，因此我们可以以其中一种属性作为物品体积，另一种属性作为价值，然后 DP 即可。
物品体积和最大价值都可能是负数。对于下标有负数的 DP ，一个常用的技巧是把所有下标加上一个定值，使得加上这个值后所有的下标都变成非负数。
另外，当物品体积是负数时，为了保证取到的是上一个物品的 DP 值，需要正序枚举背包容量。
#include<cstdio>
#include<cstring>
const int K = 400100;
int n, dp[801000], ans = 0;
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d", &n);
memset(dp, -0x3f, sizeof dp);
dp[K] = 0;
for (int i = 1; i <= n; i++) {
int a, b; scanf("%d%d", &a, &b);
if (b >= 0) for (int j = 400000; j >= -400000 + b; j--) dp[j + K] = max(dp[j + K], dp[j - b + K] + a);
else for (int j = -400000; j <= 400000 + b; j++) dp[j + K] = max(dp[j + K], dp[j - b + K] + a);
}
for (int i = 0; i <= 400000; i++)
if (dp[i + K] >= 0) ans = max(ans, dp[i + K] + i);
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P1133
先考虑序列的情况，设$dp[i][j][k]$表示第$i$个位置种了第$j$种树$(j\in{0,1,2})$，比周围位置要小$(k=0)$或大$(k=1)$。那么有：
$$dp[i][0][0]=\max(dp[i-1][1][1],dp[i-1][2][1])+a_i$$
$$dp[i][1][0]=dp[i-1][2][1]+b_i$$
$$dp[i][1][1]=dp[i-1][0][0]+b_i$$
$$dp[i][2][1]=\max(dp[i-1][0][0],dp[i-1][1][0])+c_i$$
因为$k$只可能是$0,1$交替的，所以这样是对的，并且其他没出现的状态是不合法的，无需考虑。
现在考虑环形的情况，第$1$个位置种了什么树会影响到第$n$个位置的状态是否合法，这样就有了后效性。那么可以加一维，表示第$1$个位置种了哪种树，在第$n$个位置 DP 时处理一下即可。
但实际上如果两个状态中多加的这一维不同，那么这两个状态是互不影响的，因此可以直接枚举新加的这一维的值，而不必多开一维数组，这样就省去了一些空间。
#include<cstdio>
#include<cstring>
int n, h[100100][3], dp[100100][3][2], ans;
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d%d", &h[i][0], &h[i][1], &h[i][2]);
for (int j1 = 0; j1 <= 2; j1++) {
memset(dp, 0, sizeof dp);
dp[1][j1][0] = dp[1][j1][1] = h[1][j1];
for (int i = 2; i <= n; i++) {
dp[i][0][0] = max(dp[i - 1][1][1], dp[i - 1][2][1]) + h[i][0];
dp[i][1][0] = dp[i - 1][2][1] + h[i][1];
dp[i][1][1] = dp[i - 1][0][0] + h[i][1];
dp[i][2][1] = max(dp[i - 1][0][0], dp[i - 1][1][0]) + h[i][2];
}
for (int jn = 0; jn <= 3; jn++) {
if (jn == j1) continue;
if (jn > j1) ans = max(ans, dp[n][jn][1]);
else ans = max(ans, dp[n][jn][0]);
}
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P1868
原题面题意十分不清晰，在这里写一下题意：有$n$个区间，对于区间$[x,y]$，其权值是$y-x+1$也就是区间长度，要求选择一些区间使得它们不相交，且权值和最大。
设$dp[i]$表示考虑右端点在前$i$个位置的最大权值和，那么把所有区间按照右端点排序后，直接 DP 即可。
#include<cstdio>
#include<algorithm>
int n, dp[3000100], maxr, cur = 1;
struct section {
int l, r;
bool operator < (const section &b) const { return r < b.r; }
}sc[150100];
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &sc[i].l, &sc[i].r), maxr = max(maxr, sc[i].r);
std::sort(sc + 1, sc + n + 1);
for (int i = 0; i <= maxr; i++) {
if (i >= 1) dp[i] = max(dp[i], dp[i - 1]);
while (sc[cur].r < i) cur++;
while (sc[cur].r == i){
if (sc[cur].l - 1 >= 0) dp[i] = max(dp[i], dp[sc[cur].l - 1] + sc[cur].r - sc[cur].l + 1);
else dp[i] = sc[cur].r;
cur++;
}
}
printf("%d\n", dp[maxr]);
return 0;
}https://www.luogu.com.cn/problem/P3698
这个之前那个正睿的比赛题完全相同，直接写即可。
#include<cstdio>
int n, m, d;
struct edge { int to, next; };
struct graph {
int ecnt = 1, head[110];
edge edges[210];
inline void addedge(int u, int v) {
edges[++ecnt].to = v;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}g;
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
void dfs(int x, int lst, int cnt) {
d = max(d, cnt);
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
dfs(g.edges[i].to, i, cnt + 1);
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v); u++, v++;
g.addedge(u, v), g.addedge(v, u);
}
dfs(1, 0, 0);
printf("%d\n", min(n, (m + min(m, d)) / 2 + 1));
return 0;
}https://www.luogu.com.cn/problem/P1043
设$dp[i][k]$表示前$i$个位置分成$k$个部分的最大分数，那么有：
$$dp[i][k]=\max_{j=1}^{i-1}{dp[j][k-1]+sum(j+1,i)}$$
因为是环上的问题，所以可以用破环为链的技巧。使用这种技巧的前提是问题在 DP 时考虑的是把某些区间合并起来，并且最后留下了一个没有合并起来的空隙，即最后合并成了一个环形的链，而非闭合的环，因为这个技巧的本质就是枚举最后没有合并起来的空隙的位置。
在破环为链后，每次枚举空隙的位置后都要重新 DP 一遍，因此总复杂度为$O(n^3m)$而非方程中看起来的$O(n^2m)$。
而另一种区间 DP 的写法，设$dp[i][j][k]$表示区间$[i,j]$分成$k$个部分的最大分数，然后 DP ，在破环为链后不需要重新 DP ，因为 DP 值都直接算好了，直接根据当前枚举的空隙位置取值即可。总复杂度也是$O(n^3m)$，两种做法殊途同归。
#include<cstdio>
#include<cstring>
int n, m, dp[110][10], a[110], sum[110], minans = 0x3fffffff, maxans;
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i + n] = a[i];
for (int s = 0; s < n; s++) {
memset(sum, 0, sizeof sum);
memset(dp, 0x3f, sizeof dp);
for (int i = s + 1; i <= s + n; i++) {
sum[i] = sum[i - 1] + a[i];
dp[i][1] = (sum[i] % 10 + 10) % 10;
for (int k = 2; k <= m && i - s >= k; k++) {
for (int j = s + 1; j < i; j++)
if (j - s >= k - 1) dp[i][k] = min(dp[i][k], dp[j][k - 1] * (((sum[i] - sum[j]) % 10 + 10) % 10));
}
}
minans = min(minans, dp[s + n][m]);
}
for (int s = 0; s < n; s++) {
memset(sum, 0, sizeof sum);
memset(dp, 0, sizeof dp);
for (int i = s + 1; i <= s + n; i++) {
sum[i] = sum[i - 1] + a[i];
dp[i][1] = (sum[i] % 10 + 10) % 10;
for (int k = 2; k <= m && i - s >= k; k++) {
for (int j = s + 1; j < i; j++)
if (j - s >= k - 1) dp[i][k] = max(dp[i][k], dp[j][k - 1] * (((sum[i] - sum[j]) % 10 + 10) % 10));
}
}
maxans = max(maxans, dp[s + n][m]);
}
printf("%d\n%d\n", minans, maxans);
return 0;
}