Codeforces の 动态规划

Codeforces Round 785 (Div. 2) - C. Palindrome Basis

dp(9/100)
题目链接
思路：整数划分基础上加一个判断回文的条件
整数划分思路：背包容量为n，物品有体积为1~n n种，每种无数个，求使背包恰好装满的方案数——完全背包问题（传统的背包问题可能不会恰好装满，但此问题中如果背包有空余可以用1补齐，所以是一定会装满的）

#include <bits/stdc++.h>
// #pragma GCC optimize(3,"Ofast","inline")
// #pragma GCC optimize(2)
using namespace std;
typedef long long LL;
#define int LL
const int mod = 1e9 + 7;
const int N = 4e4 + 5;
int f[N];void solve()
{ int n;cin >> n;cout << f[n] << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;cin >> t;f[0] = 1;for (int i = 1; i <= 4e4; i ++ ){string a = to_string(i);string b = a;reverse(a.begin(), a.end());if(a == b)for (int j = i; j <= 4e4; j ++ )f[j] = (f[j] + f[j - i]) % mod;			}while(t -- ) solve(); system("pause");return 0;
}

Codeforces Round 113 (Div. 2) - E. Tetrahedron

dp(18/100)
题目链接
走n步的路线数是走n-2步的三倍加上走n-1步的两倍
当走到n-2步到达D点时，还可向A B C三个方向走一来一回
例如：
f[0] = 1(没有走动，就在原点）路线：D
f[2] 路线就有：
D - A - D;
D - B - D
D - C - D
走到n-1步到达D点的情况，可在当前步向除D以外的另外两点走一步再回到D。
例如：
f[3] 路线有：
D - A - B - D
D - A - C - D
D - B - A - D
D - B - C -D
D - C - A - D
D - C- B - D

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7 + 10, mod = 1e9 + 7;
int f[N];void solve()
{int n;cin >> n;f[0] = 1;f[1] = 0;for (int i = 2; i <= n; i ++ )f[i] = (2 * f[i - 1] + 3 * f[i - 2]) % mod;cout << f[n] << endl;
}signed main()
{int t = 1;// cin >> t;while(t -- ) solve();return 0;
}