Trick
Do we really need to visit all the states?
Sometimes, the naive dp solution to a problem might take too long and too much memory. However, sometimes it is worth noting that most of the states can be ignored because they will never be reached and this can reduce your time complexity and memory complexity.
有时，问题的简单dp解决方案可能会占用太长时间和太多内存。然而，有时值得注意的是，大多数状态可以被忽略，因为它们永远不会被到达，这可以降低您的时间复杂性和内存复杂性。
Problem - C - Codeforces
Change the object to dp
更改dp的对象，选择小的dp
Problem - C - Codeforces
Problem - E - Codeforces
Open and Close Interval Trick
Problem - F - Codeforces
Problem - D - Codeforces
Problem - E - Codeforces
"Connected Component" DP
P5999 [CEOI2016] kangaroo
#include<bits/stdc++.h>
using namespace std;
long long n, m, k, i, j, f[2005][2005];
const int mod = 1e9 + 7;
int main()
{
cin >> n >> m >> k;
f[0][0] = 1;
for (i = 1; i <= n; i++)
{
for (j = 0; j <= n; j++)
{
if ((i != m) and (i != k))
{
(f[i][j] += f[i - 1][j + 1] * j) %= mod;
if (j) (f[i][j] += f[i - 1][j - 1] * (j - (i > m) - (i > k))) %= mod;
}
else
{
(f[i][j] += f[i - 1][j]) %= mod;
if (j) (f[i][j] += f[i - 1][j - 1]) %= mod;
}
}
}
cout << f[n][1] << '\n';
}
摩天大楼
#2743. 「JOI Open 2016」摩天大楼 - 题目 - LibreOJ (loj.ac)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, i, j, k, u, o, p, l, s, f[105][105][1005][3], a[105];
const int mod = 1e9 + 7;
int main()
{
cin >> n >> m;
for (i = 1; i <= n; i++)
cin >> a[i];
if (n == 1) { puts("1"); return 0; }
sort(a + 1, a + n + 1);
f[0][0][0][0] = 1;
for (i=0;i<n;i++)
for (j=0;j<=i;j++)
for (k=0;k<=m;k++)
for (u = 0; u <= 2; u++)
{
o = a[i+1] - a[i];
if (i == 0) o = 0;
p = f[i][j][k][u];
l = k + o * (j * 2 - u);
if ((l > m) or (!p))continue;
if (j > 1) (f[i + 1][j - 1][l][u] += p * (j - 1))%=mod;
(f[i + 1][j + 1][l][u] += p * (j + 1 - u))%=mod;
if (u == 0)
(f[i + 1][j + 1][l][u + 1] += p * 2)%=mod;
if (u == 1)
(f[i + 1][j + 1][l][u + 1] += p)%=mod;
(f[i + 1][j][l][u] += p * (j * 2 - u))%=mod;
if ((j)and(u == 0))
(f[i + 1][j][l][u+1] += p * 2)%=mod;
if ((j)and(u == 1))
(f[i + 1][j][l][u + 1] += p)%=mod;
}
for (i = 0; i <= m; i++)
s = (s + f[n][1][i][2])%mod;
cout << s << '\n';
}
Ant Man
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, s, e, i, j, k, q, a[5005], b[5005], c[5005], d[5005], x[5005], f[5005][5005];
int main()
{
cin >> n >> s >> e;
for (i = 1; i <= n; i++)
cin >> x[i];
for (i = 1; i <= n; i++)
cin >> a[i];
for (i = 1; i <= n; i++)
cin >> b[i];
for (i = 1; i <= n; i++)
cin >> c[i];
for (i = 1; i <= n; i++)
cin >> d[i];
for (i = 0; i <= n; i++)
for (j = 0; j <= n; j++)
f[i][j] = 1e18;
f[0][0] = 0;
for (i = 0; i < n; i++)
{
for (j = 0; j <= n; j++)
{
if ((j == 1) and (k == 2))
f[i][j] = 1e18;
if (f[i][j] < 1e18)
{
if (i + 1 == s)
{
if (j < n) f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j] + d[i + 1] - x[i + 1]);
if (j) f[i + 1][j] = min(f[i + 1][j], f[i][j] + c[i + 1] + x[i + 1]);
}
else
if (i + 1 == e)
{
if (j < n) f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j] + b[i + 1] - x[i + 1]);
if (j) f[i + 1][j] = min(f[i + 1][j], f[i][j] + a[i + 1] + x[i + 1]);
}
else
{
if (j < n) f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j] + b[i + 1] + d[i + 1] - x[i + 1] - x[i + 1]);
if (j > 1) f[i + 1][j - 1] = min(f[i + 1][j - 1], f[i][j] + a[i + 1] + c[i + 1] + x[i + 1] + x[i + 1]);
if (j)
{
if ((e > i + 1) or (j > 1)) f[i + 1][j] = min(f[i + 1][j], f[i][j] + a[i + 1] + d[i + 1]);
if ((s > i + 1) or (j > 1)) f[i + 1][j] = min(f[i + 1][j], f[i][j] + c[i + 1] + b[i + 1]);
}
}
}
}
k = k + ((i + 1 == s) or (i + 1 == e));
}
cout << f[n][1] << '\n';
}