1. Dice Combinations
统计通过扔骰子若干次可以凑出总和为 $n$ 的方案数。骰子的点数为 $1 \sim 6$
比如，如果 $n = 3$，将有 $4$ 种方式：
- $1 + 1 + 1$
- $1 + 2$
- $2 + 1$
- $3$
对答案模 $10^9 + 7$
限制：
- $1 \leqslant n \leqslant 10^6$
算法分析
记 dp[i] 表示使用 $1 \sim 6$ 之间的数可以凑出 $i$ 的方案数
转移方程：
dp[i+j] += dp[i] 1<=j<=6
三倍经验：
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::istream;
using std::ostream;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
int main() {
int n;
cin >> n;
vector<mint> dp(n+1);
dp[0] = 1;
rep(i, n) {
for (int j = 1; j <= 6; ++j) {
if (i+j <= n) dp[i+j] += dp[i];
}
}
cout << dp[n] << '\n';
return 0;
}
2. Minimizing Coins
考虑一个包含 $n$ 个硬币的金钱系统。每个硬币都有一个正整数的面值。要求使用可利用的硬币来凑出总和为 $x$ 且用的硬币数量尽可能的少。如果不可能凑出来，则输出 -1
比如，如果硬币的面值为 $\{1, 5, 7\}$ 且所需的总和为 $11$，那么最优解是 $5 + 5 + 1$，仅需 $3$ 个硬币
限制：
- $1 \leqslant n \leqslant 1000$
- $1 \leqslant x \leqslant 10^6$
- $1 \leqslant c_i \leqslant 10^6$
算法分析
完全背包
记 dp[i] 表示凑出总和为 $i$ 最少需要多少个硬币
转移方程：
$ dp[j] = \min(dp[j], dp[j-c_i] + 1) $
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
inline void chmin(int& x, int y) { if (x > y) x = y; }
int main() {
int n, x;
cin >> n >> x;
vector<int> c(n);
rep(i, n) cin >> c[i];
const int INF = 1001001001;
vector<int> dp(x+1, INF);
dp[0] = 0;
for (int v : c) {
for (int j = v; j <= x; ++j) {
chmin(dp[j], dp[j-v] + 1);
}
}
cout << (dp[x] == INF ? -1 : dp[x]) << '\n';
return 0;
}
3. 买一送一
高桥去一个比萨店买比萨。
店里有 $n$ 种比萨出售，第 $i$ 种的价格为 $p_i$ 元，美味度为 $d_i$。比萨店正在开业酬宾，每购买 $1$ 个比萨，就可以免费获得一个售价更小的比萨。
于是高桥君重复以下购买比萨的过程：
- 选择一个比萨（假设是第 $i$ 种），花费 $p_i$ 元购买第 $i$ 种比萨。
- 从价格小于 $p_i$ 元的比萨中选择一个，免费获得这个比萨。
高桥只有 $K$ 元，通过合理选择每次购买和免费获得的比萨，他最多可以得到的最大美味度的总和是多少？
限制：
- $1 \leqslant n \leqslant 300$
- $1 \leqslant K \leqslant 10000$
- $1 \leqslant p_i \leqslant K$
- $1 \leqslant d_i \leqslant 5000$
算法分析
完全背包问题
免费赠送的披萨一定选能选的价值最多的，所以只要先处理一下物品价值就可以了
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using std::cin;
using std::cout;
using std::max;
using std::vector;
inline void chmax(int& x, int y) { if (x < y) x = y; }
int dp[10005];
int main() {
int n, k;
cin >> n >> k;
vector<int> p(n+1), d(n+1);
rep(i, n) cin >> p[i] >> d[i];
vector<int> v(n+1);
rep(i, n) {
int maxd = 0;
rep(j, n) {
if (p[i] > p[j]) chmax(maxd, d[j]);
}
v[i] = d[i]+maxd;
}
rep(i, n) {
for (int j = p[i]; j <= k; ++j) {
chmax(dp[j], dp[j-p[i]] + v[i]);
}
}
cout << dp[k] << '\n';
return 0;
}
4. 假币购物
战争时期，$A$ 国制造了大量敌国 $B$ 国的假币，由间谍拿着假币到 $B$ 国购买大宗商品。
$B$ 国的货币的面值有 $n$ 种，第ii种的面值为 $m_i$，$A$ 国制造一张这样的假币的花费为 $c_i$。
在 $B$ 国有 $k$ 件大宗商品可以购买，第 $j$ 件商品的价格是 $a_j$，间谍购买时会支付总面值恰好等于价格的假币。
在造币总花费不超过 $W$ 的前提下，最多能买到的总价格是多少？
限制：
- $1 \leqslant n, k \leqslant 100$
- $1 \leqslant m_i \leqslant 1000$
- $1 \leqslant c_i \leqslant 10^5$
- $1 \leqslant W \leqslant 10^5$
- $1 \leqslant a_j \leqslant 10^5$
算法分析
先用完全背包计算出：凑出每种价格需要的最小花费。之后在总花费不超过 $W$ 的前提下，购买最多总价格的商品，也是一个完全背包
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using std::cin;
using std::cout;
using std::max;
using std::vector;
typedef long long ll;
int m[105], c[105], a[105];
int dp[105][100005], f[100005];
int w[105], v[105];
inline void chmax(int& x, int y) { if (x < y) x = y; }
inline void chmin(int& x, int y) { if (x > y) x = y; }
int main() {
int n, k, W;
cin >> n >> k >> W;
rep(i, n) cin >> m[i] >> c[i];
rep(i, k) cin >> a[i];
// dp[i][j] 是用前 i 种恰好凑出 j 的最小花费
memset(dp, 0x3f, sizeof dp);
dp[0][0] = 0;
rep(i, n) {
for (int j = 0; j <= 1e5; ++j) {
dp[i][j] = dp[i-1][j];
if (j >= m[i]) chmin(dp[i][j], dp[i][j-m[i]] + c[i]);
}
}
for (int j = 0; j <= 1e5; ++j) f[j] = dp[n][j];
memset(dp, 0, sizeof dp);
// dp[i][j] 是从前 i 件种选花费不超过 j 时，能选出的最大售价
rep(i, k) {
w[i] = f[a[i]];
v[i] = a[i];
}
rep(i, k) {
for (int j = 0; j <= W; ++j) {
dp[i][j] = dp[i-1][j];
if (j >= w[i]) chmax(dp[i][j], dp[i-1][j-w[i]] + v[i]);
}
}
cout << dp[k][W] << '\n';
return 0;
}
5. Coin Combinations I
考虑一个由 $n$ 种硬币组成的货币系统。每个硬币都有一个正整数值。
要求计算使用可用利用凑出金币总额为 $x$ 的不同方案数
举个例子，假设金币为 $\{2, 3, 5\}$，需要的总和为 $9$，那么就有 $8$ 种方案数：
- $2+2+5$
- $2+5+2$
- $5+2+2$
- $3+3+3$
- $2+2+2+3$
- $2+2+3+2$
- $2+3+2+2$
- $3+2+2+2$
限制：
- $1 \leqslant n \leqslant 100$
- $1 \leqslant x \leqslant 10^6$
- $1 \leqslant c_i \leqslant 10^6$
算法分析
注意到每种硬币可以用无限次
记 dp[w] 表示凑出 $w$ 的方案数
转移方程：
$ dp[w] = \sum\limits_{i=1}^n dp[w-c_i] $
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
mint dp[1000005];
int main() {
int n, x;
cin >> n >> x;
vector<int> c(n);
rep(i, n) cin >> c[i];
dp[0] = 1;
for (int w = 1; w <= x; ++w) {
rep(i, n) if (w >= c[i]) {
dp[w] += dp[w-c[i]];
}
}
cout << dp[x] << '\n';
return 0;
}
6. Coin Combinations II
考虑一个由 $n$ 种硬币组成的货币系统。每个硬币都有一个正整数值。
要求计算使用可用利用凑出金币总额为 $x$ 的不同有序的方案数
举个例子，假设金币为 $\{2, 3, 5\}$，需要的总和为 $9$，那么有 $3$ 种方式：
- $2+2+5$
- $3+3+3$
- $2+2+2+3$
限制：
- $1 \leqslant n \leqslant 100$
- $1 \leqslant x \leqslant 10^6$
- $1 \leqslant c_i \leqslant 10^6$
算法分析
记 dp[w] 表示凑出 $w$ 的有序方案数
转移方程：
$ dp[w] = dp[w] + dp[w-c_i] $
我们只需改变前一个问题的嵌套循环顺序。
因为我们在总和之前循环金币的种类，我们只遍历了一次金币集合，所以不可能创建两个组合，使得同一组硬币以不同顺序排列
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
mint dp[1000005];
int main() {
int n, x;
cin >> n >> x;
vector<int> c(n);
rep(i, n) cin >> c[i];
dp[0] = 1;
rep(i, n) {
for (int w = c[i]; w <= x; ++w) {
dp[w] += dp[w-c[i]];
}
}
cout << dp[x] << '\n';
return 0;
}
7. Removing Digits
给定一个整数 $n$。一次操作，你可以从这个数中减去每一位中的其中一位数。
问至少需要多少步可以将这个数变为 $0$ ？
限制：
- $1 \leqslant n \leqslant 10^6$
算法分析
贪心做法：
总是减去所有位中数字最大的那个数
dp做法：
记 dp[i] 表示将 $i$ 变成 $0$ 的最小操作次数
转移方程：
$ dp[i] = \min(dp[i], dp[i-d]), d \in \operatorname{digits}(i) $
C++ 代码
// 贪心
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int ans = 0;
while (n) {
ans++;
string s = to_string(n);
int x = 0;
for (char c : s) {
x = max(x, c-'0');
}
n -= x;
}
cout << ans << '\n';
return 0;
}
// dp
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
const int INF = 1001001001;
vector<int> dp(n+1, INF);
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
string s = to_string(i);
for (char c : s) {
dp[i] = min(dp[i], dp[i-(c-'0')]+1);
}
}
cout << dp[n] << '\n';
return 0;
}
8. Grid Paths
考虑一个 $n \times n$ 网格，其中可能有方格里存在陷阱。不允许移动到含有陷阱的格子中。
要求统计从网格左上角的格子移动到右下角的格子的不同路径数。你只能向右或向下移动。
并对结果取模
用 s[i][j] 来表示格子 $(i, j)$ 的情况
当 $s[i][j] = \’.’$，表示格子 $(i, j)$ 为空
当 $s[i][j] = \’\*\’$，表示格子 $(i, j)$ 里有陷阱
限制：
- $1 \leqslant n \leqslant 1000$
算法分析
记 dp[i][j] 表示从坐标 $(1, 1)$ 移动到坐标 $(i, j)$ 的路径数
转移方程：
$ dp[i][j] = \begin{cases} 0, & s[i][j] = \’\*\’\\\ dp[i-1][j] + dp[i][j-1], & s[i][j] = \’\.\’ \end{cases} $
C++ 代码
#include <bits/extc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
int main() {
int n;
cin >> n;
vector<string> s(n);
rep(i, n) cin >> s[i];
vector<mint> dp(n);
dp[0] = 1;
rep(i, n)rep(j, n) {
if (s[i][j] == '*') {
dp[j] = 0;
continue;
}
if (j >= 1 and s[i][j-1] == '.') {
dp[j] += dp[j-1];
}
}
cout << dp.back() << '\n';
return 0;
}
9. Book Shop
你在一家书店，这家售卖 $n$ 种不同的书。你知道每种书的价格和页数。
你已决定购买的总价格最多为 $x$。你可以买到的页数最多是多少？每种书你最多能买一次。
限制：
- $1 \leqslant n \leqslant 1000$
- $1 \leqslant x \leqslant 10^5$
- $1 \leqslant h_i, s_i \leqslant 1000$
算法分析
$01$ 背包
记 dp[i][j] 表示在前 $i$ 种书中，花费至多 $j$ 元能买到的最大页数
转移方程：
$ dp[i][j] = \max(dp[i-1][j], dp[i-1][j-h_i] + s_i) $
C++ 代码
#include <bits/extc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
inline void chmax(int& x, int y) { if (x < y) x = y; }
int main() {
int n, x;
cin >> n >> x;
vector<int> h(n), s(n);
rep(i, n) cin >> h[i];
rep(i, n) cin >> s[i];
vector<int> dp(x+1);
rep(i, n) {
for (int j = x; j >= h[i]; --j) {
chmax(dp[j], dp[j-h[i]]+s[i]);
}
}
cout << dp[x] << '\n';
return 0;
}
10. Array Description
在一个包含 $n$ 个整数的数组中，每个数的值域为 $[1, m]$，并且相邻两个数的差的绝对值不超过 $1$
在给定的数组 $x = (x_1, x_2, \cdots, x_n)$ 中有一些元素的值是未知的，用 0 来表示。
要求统计能匹配上述条件的数组个数。并对结果模 $10^9 + 7$
限制：
- $1 \leqslant n \leqslant 10^5$
- $1 \leqslant m \leqslant 100$
- $0 \leqslant x_i \leqslant m$
算法分析
记 dp[i][j] 表示在前 $i$ 个数中最后一个数填 $j$ 的合法方案数
C++ 代码
#include <bits/extc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
mint dp[100005][105];
int main() {
int n, m;
cin >> n >> m;
vector<int> x(n);
rep(i, n) cin >> x[i];
if (x[0]) dp[1][x[0]] = 1;
else {
for (int i = 1; i <= m; ++i) {
dp[1][i] = 1;
}
}
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int k = max(1, j-1); k <= min(m, j+1); ++k) {
dp[i][j] += dp[i-1][k];
}
}
if (x[i-1]) {
rep(j, m+1) {
if (j != x[i-1]) {
dp[i][j] = 0;
}
}
}
}
mint ans;
for (int i = 1; i <= m; ++i) {
ans += dp[n][i];
}
cout << ans << '\n';
return 0;
}
11. Elevator Rides
给定 $n$ 个整数 $a_1, a_2, \cdots, a_n$，再给定上限 $x$，请将这些整数分成尽量少的小组，使得每个小组的数字之和不超过 $x$，输出最少的小组数。
限制：
- $1 \leqslant n \leqslant 20$
- $1 \leqslant x \leqslant 10^9$
- $1 \leqslant a_i \leqslant x$
算法分析
状压dp
用 dp[S] 来维护两个东西，分别是可以将集合 $S$ 分成的最少组数以及最后一组的数字总和
C++ 代码
#include <bits/extc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int, int>;
template<typename T>
inline void chmin(T& x, T y) { if (x > y) x = y; }
int main() {
int n, x;
cin >> n >> x;
vector<int> a(n);
rep(i, n) cin >> a[i];
int n2 = 1<<n;
vector<P> dp(n2);
dp[0] = {1, 0};
for (int s = 1; s < n2; ++s) {
dp[s] = {20, 0};
rep(i, n) if (s>>i&1) {
P now = dp[s^(1<<i)];
if (now.second + a[i] <= x) {
now.second += a[i];
}
else {
now.first++;
now.second = a[i];
}
chmin(dp[s], now);
}
}
cout << dp.back().first << '\n';
return 0;
}
12. Edit Distance
给定两个字符串 $A$ 和 $B$，现在要将 $A$ 经过若干操作变为 $B$，可进行的操作有：
- 在字符串 $A$ 中的某个位置插入某个字符
- 将字符串 $A$ 中的某个字符删除
- 将字符串 $A$ 中的某个字符替换为另一个字符
现在请你求出，将 $A$ 变为 $B$ 至少需要进行多少次操作。
其中 $A$ 的长度为 $n$，$B$ 的长度为 $m$
限制：
- $1 \leqslant n, m \leqslant 5000$
算法分析
记 dp[i][j] 表示将 $a[1 \sim i]$ 变成 $b[1 \sim j]$ 的最小操作次数
转移方程：
1). 删：$dp[i-1][j-1] + 1$
2). 增：$dp[i][j-1] + 1$
3). 改：$dp[i-1][j-1] + (a_i \neq b_j)$
综上可得，$dp[i][j] = \min\{dp[i-1][j-1] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + (a_i \neq b_j)\}$
时间复杂度：$O(n^2)$
C++ 代码
#include <bits/extc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
const int INF = 1001001001;
int dp[5005][5005];
inline void chmin(int& x, int y) { if (x > y) x = y; }
int main() {
string a, b;
cin >> a >> b;
int n = a.size(), m = b.size();
rep(i, m+1) dp[0][i] = i; // 添加
rep(i, n+1) dp[i][0] = i; // 删除
rep(i, n)rep(j, m) {
int now = INF;
chmin(now, dp[i][j+1]+1);
chmin(now, dp[i+1][j]+1);
chmin(now, dp[i][j]+(a[i] != b[j]));
dp[i+1][j+1] = now;
}
cout << dp[n][m] << '\n';
return 0;
}
13. 间距数列
满足以下条件的长为 $n$ 的整数序列 $a_1, a_2, \cdots, a_n$ 有多少个？
- $1 \leqslant a_i \leqslant m$，$1 \leqslant i \leqslant n$
- $|a_i-a_{i+1}| \geqslant k\ (1 \leqslant i \leqslant n-1)$
输出答案除以 $998244353$ 的余数。
限制：
- $2 \leqslant n \leqslant 1000$
- $1 \leqslant m \leqslant 5000$
- $0 \leqslant k \leqslant m-1$
算法分析
记 dp[i][j] 表示长为 $i$ 的结尾等于 $j$ 的数列个数
转移方程：
$ dp[i][j] = （dp[i-1][1] + \cdots + dp[i-1][j-k]） + (dp[i-1][j+k] + \cdots + dp[i-1][m]) $
然后用前缀和去优化
记 s[i][j] 表示长为 $i$ 且结尾 $\leqslant j$ 的数列个数
初始值：
$dp[1][1 \sim m] = 1$
$s[1][j] = j$
还需特判一下 $k = 0$ 的情况，答案是 $m^n$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
using ll = long long;
const int mod = 998244353;
//const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
mint dp[1005][5005];
mint s[1005][5005];
int main() {
int n, m, k;
cin >> n >> m >> k;
if (k == 0) {
cout << mint(m).pow(n) << '\n';
return 0;
}
rep(j, m) dp[1][j] = 1;
rep(j, m) s[1][j] = j;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
mint now;
if (j-k >= 0) now += s[i-1][j-k];
if (j+k-1 <= m) now += s[i-1][m] - s[i-1][j+k-1];
dp[i][j] = now;
s[i][j] = s[i][j-1] + now;
}
}
mint ans;
rep(j, m) {
ans += dp[n][j];
}
cout << ans << '\n';
return 0;
}
14. 异或值的数量
给定整数 $n,m$ 以及一维数组 $arr$，从数组 $arr$ 中取若干元素求异或和，共能得到 $2^n$ 个结果($n$ 为 $arr$ 的大小)，请求出这些结果中大于 $m$ 的有多少个，输出结果对 $1000000007$ 取模。
限制：
- $1 \leqslant n, m \leqslant 10000$
- $1 \leqslant arr[i] \leqslant 800$
- 内存限制只有
32M
算法分析
记 dp[i][j] 表示前 $i$ 个数中选出的数的异或和为 $j$ 的方案数
转移方程：
$ dp[i][j] = dp[i-1][j] + dp[i-1][j \oplus a_i] $
注意要压一下空间
C++ 代码
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
class Solution {
public:
/**
* @param n: The number of integers
* @param m: The lim of xor values
* @param arr: The integer values
* @return: Please calculate the number of xor values that greater than m ,and output the answer modulo 1000000007
*/
int getAns(int n, int m, vector<int> &a) {
const int M = 1024;
vector<mint> dp(M);
dp[0] = 1;
for (int i = 0; i < n; ++i) {
vector<mint> p(M);
swap(dp, p);
for (int j = 0; j < M; ++j) {
dp[j] += p[j] + p[j^a[i]];
}
}
mint res;
for (int i = m+1; i < M; ++i) {
res += dp[i];
}
return res.x;
}
};
15. 子集合（四）
子集和问题是指，给定 $n$ 个数字 $a_1,a_2,\cdots, a_n$ ，再给定一个目标 $t$，有多少种方法，能够选出一些数字，使得它们的和等于 $t$。在这道题目中，每个数字可以重复使用任意多次。
小爱希望计算一些带有限制的子集和问题，她想知道，如果规定不能选择 $a_i$，那么还有多少种方法，可以选出一些数字，使得它们的和等于目标 $t$？
限制：
- $1 \leqslant n \leqslant 5000$
- $1 \leqslant a_i \leqslant 10000$
- $1 \leqslant t \leqslant 10000$
算法分析
可以先求出由这 $n$ 个数组成 $t$ 的方案数，这是简单的完全背包问题
记 dp[t] 表示组成 $t$ 的方案数
不选择 $a_i$ 的前提下组成 $t$ 的方案数也就是把 $dp[t]$ 减掉至少包含一个 $a_i$ 的方案
回想一下：$dp[t-a_i] \to dp[t]$
所以每个问题的答案就是 $dp[t] - dp[t-a_i]$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::istream;
using std::ostream;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
mint dp[10005];
int main() {
int n, t;
cin >> n >> t;
vector<int> a(n);
rep(i, n) cin >> a[i];
dp[0] = 1;
rep(i, n) {
for (int j = 0; j <= t-a[i]; ++j) {
dp[j+a[i]] += dp[j];
}
}
// 考虑减掉至少包含一个 a[i] 的方案
rep(i, n) {
if (t >= a[i]) {
dp[t] -= dp[t-a[i]];
}
cout << dp[t] << '\n';
if (t >= a[i]) {
dp[t] += dp[t-a[i]];
}
}
return 0;
}
16. K数之和
给定 $n$ 个不同的正整数，整数 $k(k \leq n)$ 以及一个目标数字 target。
在这 $n$ 个数里面找出 $k$ 个数，使得这 $k$ 个数的和等于目标数字，求问有多少种方案？
算法分析
二维费用背包计数
记 dp[i][j][k] 表示从前 $i$ 个数中选出 $j$ 个数满足总和为 $k$ 的方案数
C++ 代码
class Solution {
public:
/**
* @param a: An integer array
* @param k: A positive integer (k <= length(A))
* @param target: An integer
* @return: An integer
*/
int kSum(vector<int> &a, int K, int m) {
int n = a.size();
vector<vector<int>> dp(K+1, vector<int>(m+1));
dp[0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = K; j >= 1; --j) {
for (int k = m; k >= a[i]; --k) {
dp[j][k] += dp[j-1][k-a[i]];
}
}
}
return dp[K][m];
}
};
17. Traveling Salesman Problem
在二维平面上有 $N$ 个城市，分别编号为 $1, 2, \cdots, N$ 。
第 $i$ 个城市的坐标为 $(X_i, Y_i)$，在两个城市之间移动的时间和它们之间的直线距离相同。
即，从第 $i$ 个城市移动到第 $j$ 个城市将花费 $\sqrt{(X_i-X_j)^2 + (Y_i-Y_j)^2}$ 分钟。
问：从一个城市出发，经过所有城市后，最快需要几分钟才能回到出发地？
限制：
- $2 \leqslant N \leqslant 15$
- $0 \leqslant X_i \leqslant 1000$
- $0 \leqslant Y_i \leqslant 1000$
算法分析
状压DP
记 dp[S][v] 表示已经访问过的城市集合为 $S$ 且最后一个访问的城市是 $v$ 所需的最短时间
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
// Geometry
const double eps = 1e-9;
bool equal(double a, double b) { return abs(a-b) < eps;}
// Vector
struct V {
double x, y;
V(double x=0, double y=0): x(x), y(y) {}
V& operator+=(const V& v) { x += v.x; y += v.y; return *this;}
V operator+(const V& v) const { return V(*this) += v;}
V& operator-=(const V& v) { x -= v.x; y -= v.y; return *this;}
V operator-(const V& v) const { return V(*this) -= v;}
V& operator*=(double s) { x *= s; y *= s; return *this;}
V operator*(double s) const { return V(*this) *= s;}
V& operator/=(double s) { x /= s; y /= s; return *this;}
V operator/(double s) const { return V(*this) /= s;}
double dot(const V& v) const { return x*v.x + y*v.y;}
double cross(const V& v) const { return x*v.y - v.x*y;}
double norm2() const { return x*x + y*y;}
double norm() const { return sqrt(norm2());}
V rotate90() const { return V(y, -x);}
int ort() const { // orthant
if (abs(x) < eps && abs(y) < eps) return 0;
if (y > 0) return x>0 ? 1 : 2;
else return x>0 ? 4 : 3;
}
bool operator<(const V& v) const {
int o = ort(), vo = v.ort();
if (o != vo) return o < vo;
return cross(v) > 0;
}
};
istream& operator>>(istream& is, V& v) {
is >> v.x >> v.y; return is;
}
ostream& operator<<(ostream& os, const V& v) {
os<<"("<<v.x<<","<<v.y<<")"; return os;
}
inline void chmin(double& x, double y) { if (x > y) x = y; }
int main() {
int n;
cin >> n;
vector<V> p(n);
rep(i, n) cin >> p[i];
vector dist(n, vector<double>(n));
rep(i, n)rep(j, n) dist[i][j] = (p[i]-p[j]).norm();
int n2 = 1<<n;
const double INF = 1e18;
vector dp(n2, vector<double>(n, INF));
dp[0][0] = 0;
rep(s, n2)rep(v, n) {
if (dp[s][v] == INF) continue;
rep(u, n) {
if (s>>u&1) continue;
chmin(dp[s|1<<u][u], dp[s][v]+dist[v][u]);
}
}
printf("%.10f\n", dp[n2-1][0]);
return 0;
}
18. 围三角
二维01布尔背包
若已知三角形的三条边，我们可以通过海伦公式计算出面积
记 dp[i][j][k] 表示用前 $i$ 条线段拼出三角形的其中两条边分别为 $j$ 和 $k$ 的可行性
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const int MX = 1605;
bool dp[MX][MX];
inline void chmax(ll& x, ll y) { if (x < y) x = y; }
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
int s = 0;
rep(i, n) s += a[i];
int m = s/2;
dp[0][0] = true;
rep(i, n) {
for (int j = m; j >= 0; --j) {
for (int k = j; k >= 0; --k) {
if (dp[j][k]) {
dp[j+a[i]][k] = dp[j][k+a[i]] = true;
}
}
}
}
auto area = [&](int x, int y, int z) {
ll p = x+y+z;
return p * (p-2*x) * (p-2*y) * (p-2*z);
};
ll ans = 0;
for (int i = m; i >= 0; --i) {
for (int j = i; j >= 0; --j) { //如果 边长 i，j能够成三角形的两边，第三边肯定是剩下的所有数之和 s - i - j
if (dp[i][j]) {
chmax(ans, area(i, j, s-i-j));
}
}
}
cout << ans << '\n';
return 0;
}
19. 炼制合金
二维费用01背包
记 dp[i][j][k] 表示从前 $i$ 块材料中挑选若干块材料满足总共有 $j$ 克黄金和 $k$ 克白银所需支付的最小费用
C++ 代码
#include <bits/extc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int dp[305][305];
inline void chmin(int& x, int y) { if (x > y) x = y; }
int main() {
int n, a, b;
cin >> n >> a >> b;
const int INF = 1001001001;
rep(i, a+1)rep(j, b+1) dp[i][j] = INF;
dp[0][0] = 0;
rep(i, n) {
int x, y, w;
cin >> x >> y >> w;
for (int j = a; j >= 0; --j) {
for (int k = b; k >= 0; --k) {
int nj = min(a, j+x);
int nk = min(b, k+y);
chmin(dp[nj][nk], dp[j][k]+w);
}
}
}
cout << dp[a][b] << '\n';
return 0;
}
20. 最长锯齿子序列
给定 $n$ 个整数组成的序列 $a_1,~a_2,~\cdots,~a_n$，请从中挑出尽量长的子序列，形成一个锯齿序列。所谓锯齿序列，就是它的差分序列（由相邻数字的差组成的序列）是正负交替的。为了避免差为 $0$ 时不方便区分正负，保证给定的每个数字都不相同。
例如给定的序列是 $1,~3,~5,~2,~4,~6$，那么它的子序列 $1,~5,~2,~6$ 是一个锯齿序列，因为它的差分序列是 $4,~-3,~4$；而 $1,~3,~5$ 不是，因为这三个数字是递增的。
求最长的锯齿子序列长度。
限制：
- $1 \leqslant n \leqslant 10^4$
- $1 \leqslant a_i \leqslant 10^5$
算法分析
LIS 变种
状态表示：
dp[i][0] 表示最后一个数是下降的最长锯齿子序列长度
dp[i][1] 表示最后一个数是上升的最长锯齿子序列长度
C++ 代码
#include <bits/extc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
inline void chmax(int& x, int y) { if (x < y) x = y; }
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
int ans = 0;
vector dp(n, vector<int>(2));
rep(i, n) {
dp[i][0] = dp[i][1] = 1;
rep(j, i) {
if (a[i] < a[j]) chmax(dp[i][0], dp[j][1]+1);
else chmax(dp[i][1], dp[j][0]+1);
}
chmax(ans, dp[i][0]);
chmax(ans, dp[i][1]);
}
cout << ans << '\n';
return 0;
}
21. 固定和的倍数序列
如果一个数列 $a_1,a_2,\cdots,a_n$ 满足以下条件，则称它是一个“倍数序列”：
- 所有元素都是正整数。
- 对于 $2 \le i \le n$，$a_i$ 是 $a_{i-1}$ 的倍数。
求元素总和 $a_1+a_2+\cdots+a_n$ 等于 $M$ 的“倍数序列”个数。个数可能很大，你只需输出答案除以 $10^9+7$ 的余数。
限制：
- $1 \leqslant M \leqslant 10^5$
算法分析
设 $a_i = k_ia_{i-1}$，某一倍数序列长度为 $n$，则元素总和可以写作：
$ \begin{aligned} \sum_{i=1}^n a_i &= a_1 + k_2a_1 + k_3k_2a_1 + \cdots + k_nk_{n-1}\cdots k_2a_1\\ &= a_1(1 + k_2 + k_3k_2 + \cdots + k_nk_{n-1} \cdots k_2) = M \end{aligned} $
可得 $k_2 + k_3k_2 + \cdots + k_nk_{n-1} \cdots k_2 = \frac{M}{a_1} - 1$，这一式子是求出状态转移方程的关键。
其表明：固定 $a_1$，则一个元素总和为 $M$ 的倍数序列，与一个元素总和为 $\frac{M}{a_1} - 1$ 的倍数序列一一对应。
状态：
- 要区分出两种倍数序列的元素总和。
- $dp[i]$：和为 $i$ 的倍数序列的数量。
转移：
- 任取 $i$ 的约数 $j$，则 $j$ 可以作为倍数序列的第一项 $a_1$。
- 所有元素总和为 $i$ 的倍数序列，按照 $a_1$ 分类，该分类方法不重复、不遗漏。
方程：
$$ dp[i] = \sum_{j \big| i} dp[\frac{i}{j}-1] $$
细节：
- 初始条件：$dp[0] = 1$
- 状态转移方程中的 $j$ 是 $i$ 的约数，而约数是成对出现的，因此没有必要枚举到底。
- 要注意一对两个约数都是某一完全平方数的平方根的情形，不要重复计数。
时间复杂度：$O(n\sqrt{n})$
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
mint dp[100005];
int main() {
int m;
cin >> m;
dp[0] = 1;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j*j <= i; ++j) {
if (i%j) continue;
dp[i] += dp[i/j-1];
if (j != i/j) dp[i] += dp[j-1];
}
}
cout << dp[m] << '\n';
return 0;
}
递推/填表法 $\to$ 递拉/刷表法
- 不是对于等号左边的项，将右边所有的项加起来
- 而是对于等号右边的项，考虑它要加到左边的哪些项上。
观察方程 $dp[i] = \sum_{j \big| i} dp[\frac{i}{j}-1]$，以 $\frac{i}{j}$ 为主元，可以改写成：
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= m/i; ++j) {
dp[i*j] += dp[i-1];
}
}
统计双重循环操作次数，有:
$$M(1 + \frac{1}{2} + \cdots + \frac{1}{M}) = M\sum_{i=1}^M \frac{1}{i}$$
在数学上，$\sum\limits_{i=1}^{+\infty} \frac{1}{i}$ 称为调和级数。
由阶的估计的知识，$\sum\limits_{i=1}^M \frac{1}{i} = \mathcal{O}(\log M)$ 。
22. abc222d
给定两个单调不下降的序列 $a$ 和 $b$，求单调不下降序列 $c$，满足 $a_i\le c_i\le b_i$ 的数量。并对结果模 $998244353$。
限制：
- $1 \leqslant n \leqslant 3000$
- $0 \leqslant a_i \leqslant b_i \leqslant 3000$
算法分析
记 dp[i][j] 表示考察到 $C_i$ 时，$C_i = j$ 的合法方案数
转移方程：
$ dp[i][j] = \begin{cases} \sum\limits_{k \leqslant j} dp[i - 1][j], & a[i] \leqslant j \leqslant b[i] \\\ 0, & \text{其他} \end{cases} $
此时状态数为 $O(NM)$，转移数为 $O(M)$，所以总的时间复杂度为 $O(NM^2)$，显然会超时
下面考虑优化：
对于 $\sum\limits_{k \leqslant j} dp[i - 1][j]$ 这部分可以用前缀和来加速
代码实现
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using mint = modint998244353;
int main() {
int n;
cin >> n;
vector<int> a(n), b(n);
rep(i, n) cin >> a[i];
rep(i, n) cin >> b[i];
const int M = 3001;
vector<mint> dp(M);
dp[0] = 1;
rep(i, n) {
vector<mint> p(M);
swap(dp, p);
rep(j, M - 1) p[j + 1] += p[j];
rep(j, M) {
if (a[i] <= j and j <= b[i]) {
dp[j] += p[j];
}
}
}
mint ans;
rep(i, M) ans += dp[i];
cout << ans.val() << '\n';
return 0;
}
23. 分段求平均数
本题难度中等，划分型DP问题。用 dp[i] 表示前 $i$ 个数最少划分成几段，对 $j = 1, 2, \cdots, i-1$ 判断从 $a_j$ 到 $a_i$ 划分成一段时，平均数是否为整数，如果是整数，就更新 $dp[i] = \max(dp[i], dp[j-1]+1)$
初始值: $dp[i] = i$
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<int> s(n+1);
rep(i, n) s[i+1] = s[i]+a[i];
vector<int> dp(n+1);
rep(i, n+1) dp[i] = i;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
if ((s[i]-s[j-1])%(i-j+1) == 0) {
dp[i] = min(dp[i], dp[j-1]+1);
}
}
}
cout << dp[n] << '\n';
return 0;
}
24. 可被三整除的最大和
记 dp[i][j] 表示从前 $i$ 个数中选出若干个数，并且它们的总和模 $3$ 余 $j (0 \leqslant j < 3)$ 时，这些数的和的最大值
初始值：dp[0][0] = 0，其他 $dp = -\infty$
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
int n = nums.size();
vector dp(n+1, vector<int>(3, INT_MIN));
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 3; ++j) {
dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
int nj = (j+nums[i]%3)%3;
dp[i+1][nj] = max(dp[i+1][nj], dp[i][j]+nums[i]);
}
}
return dp[n][0];
}
};
25. LC1681 最小不兼容性
状压dp
记 dp[mask] 表示已经分配过的元素集合的不兼容性之和的最小值
具体分析见官方题解
C++ 代码
class Solution {
public:
int minimumIncompatibility(vector<int>& nums, int k) {
int n = nums.size();
int group = n/k;
unordered_map<int, int> mp;
int n2 = 1<<n;
for (int mask = 1; mask < n2; ++mask) {
if (__builtin_popcount(mask) != group) continue;
int mn = 20, mx = 0;
unordered_set<int> s;
for (int i = 0; i < n; ++i) {
if (mask>>i&1) {
if (s.count(nums[i])) break;
s.insert(nums[i]);
mn = min(mn, nums[i]);
mx = max(mx, nums[i]);
}
}
if (s.size() == group) mp[mask] = mx-mn;
}
constexpr int INF = 1001001001;
vector<int> dp(n2, INF);
dp[0] = 0;
for (int mask = 0; mask < n2; ++mask) {
if (dp[mask] == INF) continue;
unordered_map<int, int> used;
for (int i = 0; i < n; ++i) {
if (~mask>>i&1) used[nums[i]] = i;
}
if (used.size() < group) continue;
int sub = 0;
for (auto& p : used) sub |= 1<<p.second;
int nxt = sub;
while (nxt) {
if (mp.count(nxt)) {
dp[mask|nxt] = min(dp[mask|nxt], dp[mask]+mp[nxt]);
}
nxt = (nxt-1)⊂
}
}
int res = dp.back();
if (res == INF) res = -1;
return res;
}
};
26. LC1434 每个人戴不同帽子的方案数
状压dp
记 dp[i][mask] 表示我们处理了前 $i$ 顶帽子，并且已经被分配帽子的人的状态为 $mask$ 时的方案数
C++ 代码
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
class Solution {
public:
int numberWays(vector<vector<int>>& hats) {
int n = hats.size();
int maxHatId = 0;
for (int i = 0; i < n; ++i) {
for (int h : hats[i]) {
maxHatId = max(maxHatId, h);
}
}
vector<vector<int>> hatToPerson(maxHatId+1);
for (int i = 0; i < n; ++i) {
for (int h : hats[i]) {
hatToPerson[h].push_back(i);
}
}
int n2 = 1<<n;
vector<mint> dp(n2);
dp[0] = 1;
for (int i = 1; i <= maxHatId; ++i) {
vector<mint> p = dp;
for (int mask = 0; mask < n2; ++mask) {
for (int j : hatToPerson[i]) {
if (mask>>j&1) dp[mask] += p[mask^(1<<j)];
}
}
move(p);
}
return dp.back().x;
}
};
27. 完美匹配
记 dp[i][S] 表示到第 $i$ 个黑点为止已经配对的白点集合为 $S$ 的二分图完美匹配数
容易发现只有当 $|S| = i$ 时才有意义，所以我们可以把 $\operatorname{dp}$ 的第一维压掉
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
int main() {
int n;
cin >> n;
vector a(n, vector<int>(n));
rep(i, n)rep(j, n) cin >> a[i][j];
int n2 = 1<<n;
vector<mint> dp(n2);
dp[0] = 1;
rep(s, n2) {
int i = __builtin_popcount(s);
rep(j, n) if (~s>>j&1) {
if (a[i][j]) dp[s|1<<j] += dp[s];
}
}
cout << dp.back() << '\n';
return 0;
}
28. Number of Subsequences
dp[i][0] 表示前 $i$ 个字符中空字符出现的次数
dp[i][1] 表示前 $i$ 个字符中 a 出现的次数
dp[i][2] 表示前 $i$ 个字符中 ab 出现的次数
dp[i][3] 表示前 $i$ 个字符中 abc 出现的次数
当 $S_i$ 不为 ? 时，正常递推即可
当 $S_i$ 为 ? 时，由于它可以变成 a/b/c 这三种字符，所以会额外增加 $3$ 个字符串。
递推的时候需要适当的乘以 $3$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
// const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
int main() {
int n;
string s;
cin >> n >> s;
vector dp(n + 1, vector<mint>(4));
dp[0][0] = 1;
rep(i, n) {
dp[i + 1] = dp[i];
if (s[i] == 'a') dp[i + 1][1] += dp[i][0];
if (s[i] == 'b') dp[i + 1][2] += dp[i][1];
if (s[i] == 'c') dp[i + 1][3] += dp[i][2];
if (s[i] == '?') {
dp[i + 1][0] = dp[i][0] * 3;
dp[i + 1][1] = dp[i][1] * 3 + dp[i][0];
dp[i + 1][2] = dp[i][2] * 3 + dp[i][1];
dp[i + 1][3] = dp[i][3] * 3 + dp[i][2];
}
}
cout << dp[n][3].x << '\n';
return 0;
}
29. 单词解密
记 dp[i] 表示将 $s$ 的前 $i$ 个字符转化为明文的方案数
转移方程：
如果 $1 \leqslant s_i \leqslant 9$，则可以直接转化为 $a \sim i$
$\Rightarrow$ dp[i+1] += dp[i]
如果 $10 \leqslant \overline{s_{i-1}s_i} <= 26$,则可以将这两个字符转成 $j \sim z$
$\Rightarrow$ dp[i+1] += dp[i-1]
初始化：$dp[0] = 1$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
int main() {
string s;
cin >> s;
int n = s.size();
vector<mint> dp(n+1);
dp[0] = 1;
rep(i, n) {
if (s[i] != '0') dp[i+1] += dp[i];
if (i >= 1) {
string t = s.substr(i-1, 2);
if ("10" <= t and t <= "26") dp[i+1] += dp[i-1];
}
}
cout << dp[n] << '\n';
return 0;
}
30. 升序排列（二）
排列 $p$ 中的最长连续子序列是不需要移动的，只需移动剩下的数即可
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
cin >> n;
vector<int> p(n);
rep(i, n) cin >> p[i];
int len = 0;
vector<int> dp(n+1);
for (int x : p) {
dp[x] = dp[x-1]+1;
len = max(len, dp[x]);
}
cout << n-len << '\n';
return 0;
}
31. 排列计数（二）
记 dp[i][j] 表示到第 $i$ 个数为止最后一个数为 $j$ 的合法排列数
当 si == '<' 时，最后一位的 $j$ 必须大于前一位的数字 $k$，$\Rightarrow ~ dp[i][j] = \sum\limits_{k=1}^{j-1} dp[i-1][k]$
当 si == '?' 时，最后一位的 $j$ 和前面一位的数字 $k$ 没有任何限制关系，$\Rightarrow ~ dp[i][j] = \sum\limits_{k=1}^{i-1} dp[i-1][k]$
当 si == '>' 时，最后一位的 $j$ 必须小于前一位的数字 $k$，可以用总方案数容斥掉最后一位满足 < 的方案数 $\Rightarrow ~ dp[i][j] = \sum\limits_{k=1}^{i-1} dp[i-1][k] - \sum\limits_{k=1}^{j-1} dp[i-1][k]$
最后的答案为 $\sum\limits_{i=1}^n dp[n][i]$
但这种做法的时间复杂度为 $\mathcal{O}(n^3)$
我们可以用前缀和将复杂度降到 $\mathcal{O}(n^2)$
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
mint dp[1005][1005], ds[1005][1005];
int main() {
string s;
cin >> s;
int n = s.size()+1;
dp[1][1] = ds[1][1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
if (s[i-2] == '?') dp[i][j] = ds[i-1][i-1];
if (s[i-2] == '>') dp[i][j] = ds[i-1][j-1];
if (s[i-2] == '<') dp[i][j] = ds[i-1][i-1] - ds[i-1][j-1];
ds[i][j] = ds[i][j-1] + dp[i][j];
}
}
cout << ds[n][n] << '\n';
return 0;
}
32. 运输
$\operatorname{sosdp}$
记 dp[S] 表示将集合 $S$ 中的所有非 $0$ 数加到一个数上的最小操作次数
转移方程：
$$ dp[S] = \min\{dp[S-{x}] + \big(\sum_{i \in S} a_i - a_x \neq 0\big)\}, ~ x \in S $$
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
inline void chmin(int& a, int b) { if (a > b) a = b; }
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
int n2 = 1<<n;
vector<int> dp(n2, n);
dp[0] = 0;
for (int s = 1; s < n2; ++s) {
int tot = 0;
rep(i, n) if (s>>i&1) tot += a[i];
rep(i, n) if (s>>i&1) {
chmin(dp[s], dp[s^(1<<i)] + (tot-a[i] != 0));
}
}
cout << dp.back() << '\n';
return 0;
}
33. 子集的并
设 $A=\{1,2,\cdots,n\}$，给定 $m$ 个集合 $S_1, S_2, \cdots, S_m$，每个集合都是 $A$ 的子集，我们希望从这些集合中选出一些，使得它们的并集等于 $A$，请统计有多少种不同的选择方案？答案可能很大，取模 $10^9+7$ 的余数。
限制：
- $1 \leqslant n \leqslant 22$
- $1 \leqslant m \leqslant 10^5$
算法分析
记 $f(U)$ 表示集合 $U$ 包含多少个集合 $S$，那么选取若干个集合 $S$ 使得它们的并集成为集合 $U$ 的子集的方案数就是 $2^{f(U)}$，然后运用容斥原理就可以求出答案
对于 $f(U)$，我们可以通过 $\operatorname{sosdp}$ 预处理出来。
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n, m;
cin >> n >> m;
int n2 = 1<<n;
vector<int> a(n2);
rep(i, m) {
int k;
cin >> k;
int s = 0;
rep(j, k) {
int x;
cin >> x;
--x;
s |= 1<<x;
}
a[s]++;
}
rep(i, n)rep(s, n2) {
if (s>>i&1) a[s] += a[s^(1<<i)];
}
vector<mint> pow2(m+1, 1);
rep(i, m) pow2[i+1] = pow2[i]*2;
mint ans;
rep(s, n2) {
if (__builtin_parity(s) == (n&1)) ans += pow2[a[s]];
else ans -= pow2[a[s]];
}
cout << ans << '\n';
return 0;
}
34. 摄像头安装
在一条大街上，开了 $n$ 家商店，我们需要从这些商店里，选择一部分商店，安装摄像头。第 $i$ 家商店安装摄像头的费用为 $c_i$。请问应该选择哪些商店安装摄像头，使得任意 $m$ 家连续的商店里，都至少拥有两个摄像头，并输出安装摄像头的最小总费用。
限制：
- $2 \leqslant m \leqslant n \leqslant 5000$
- $1 \leqslant c_i \leqslant 10000$
算法分析
记 dp[i][j] 表示在前 $i$ 家商店中，将最后一个摄像头安装在第 $i$ 家商店，且将倒数第二个摄像头安装在第 $j$ 家商店，其中 $i-m < j < i$
转移方程：
$ dp[i][j] = \min(dp[j][k]+a_i) $，其中 $i-m \leqslant k < j$
但这样做的时间复杂度为 $\mathcal{O}(n^3)$
我们可以考虑倒序遍历 $j$，同时钦定点 $i-m$ 是使得 $dp[j][k]$ 取得最小值点的位置
于是，时间复杂度就降到了 $\mathcal{O}(n^2)$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
inline void chmin(int& a, int b) { if (a > b) a = b; }
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n+1);
rep(i, n) cin >> a[i];
const int INF = 1001001001;
vector dp(n+1, vector<int>(n+1, INF));
rep(i, n) dp[i][0] = a[i];
for (int i = 2; i <= n; ++i) {
int k = max(0, i-m);
int now = dp[i-1][k];
for (int j = i-1; j > k; --j) {
chmin(now, dp[j][k]);
chmin(dp[i][j], now+a[i]);
chmin(dp[i][j-1], dp[i][j]);
}
}
int ans = INF;
for (int i = n-m+2; i <= n; ++i) chmin(ans, dp[i][n-m+1]);
cout << ans << '\n';
return 0;
}
35. 排版问题
由于英文单词长短不一，对一篇文章进行排版的时候，如何把文章中的单词分在不同的行上可以达到整齐美观的效果，是一个大问题。
给定一个整数 $n$，表示一篇需要排版的文章有 $n$ 个单词，其中第 $i$ 个单词有 $w_i$ 个字母，请将这些单词分成若干行，使得整篇文章的偏离度到达最小。
整篇文章排版的偏离度定义为每一行的偏离度之和。一行的偏离度定义为 $(x-a)^2$，其中 $a$ 为一个给定的标准长度，$x$ 为这一行单词的字母数量之和。
限制：
- $1 \leqslant n \leqslant 2 \times 10^5$
- $1 \leqslant a \leqslant 10^5$
- $1 \leqslant w_i \leqslant 100$
算法分析
记 $s_i$ 表示前 $i$ 个单词的长度总和，dp[i] 表示将前 $i$ 个单词分成若干段得到的最小排版偏离度
转移方程：
$ dp[i] = \min\{dp[j] + (s_i - s_j - a)^2\} $
记 $c_i = s_i-a$，则有 $ dp[i] = \min\{dp[j] + (c_i - s_j)^2\} $
现在仅考察右式，并将 $\min$ 去掉
$dp[j] + (c_i - s_j)^2 = dp[j] + c_i^2 - 2c_is_j + s_j^2 = -2s_j \cdot c_i + (dp[j] + s_j^2) + c_i^2$
不妨记 $A_j = -2s_j, B_j = dp[j]+s_j^2$
那么，则有 $dp[i] = \min\{A_jc_i + B_j + c_i^2\}$
然后用 $\operatorname{cht}$ 加速即可
时间复杂度为 $\mathcal{O}(n)$
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
// Convex Hull Trick
struct CHT {
struct Linear {
ll a, b;
Linear(ll a=0, ll b=0): a(a), b(b) {}
ll operator()(ll x) const { return a*x+b; }
};
deque<Linear> ls;
void add(ll a, ll b) { // decreasing order of a
Linear l(a, b);
assert(ls.size() == 0 or ls.back().a >= l.a);
while (ls.size() >= 2) {
const Linear& l1 = ls[ls.size()-2];
const Linear& l2 = ls.back();
if ((l.b-l2.b)*(l1.a-l2.a) > (l2.a-l.a)*(l2.b-l1.b)) break;
ls.pop_back();
}
ls.push_back(l);
}
ll operator()(ll x) {
while (ls.size() >= 2) {
ll a = ls[0](x);
ll b = ls[1](x);
if (a < b) break; // get min
ls.pop_front();
}
return ls[0](x);
}
};
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n, a;
cin >> n >> a;
vector<ll> w(n);
rep(i, n) cin >> w[i];
rep(i, n-1) w[i+1] += w[i];
vector<ll> c(n);
rep(i, n) c[i] = w[i]-a;
CHT cht;
cht.add(0, 0);
ll ans = 0;
rep(i, n) {
ans = cht(c[i]);
ans += c[i]*c[i];
cht.add(-2*w[i], ans+w[i]*w[i]);
}
cout << ans << '\n';
return 0;
}
36. 分割数列
给定 $n$ 个数字 $a_1,a_2,\dots,a_n$，可以将它分割成任意多段，每一段可以有任意多个数字，唯一的要求是每段的数字之和都要大于或等于 $0$。
请问有多少种分段方法？由于答案可能很大，输出方案数模 $1,000,000,007$ 的余数。
例如当数列为 $1,~-2,~3,~-1$ 时，只有两种合适的分割方案：
- $(1,−2,3,−1)$
- $(1),~(−2,3,−1)$
限制：
- $1 \leqslant n \leqslant 2 \times 10^5$
- $|a_i| \leqslant 10^6$
算法分析
记 $s_k = \sum\limits_{i=1}^k a_i$
状态表示：dp[i] 表示将前 $i$ 个数分割成若干段的合法分割方案数
转移方程：$dp[i] = \displaystyle\sum_{j=0}^{i-1} [s_j \leqslant s_i]dp[j]$
时间复杂度为 $\mathcal{O}(n^2)$
可以通过离散化+树状数组优化到 $\mathcal{O}(n\log n)$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
template<typename T>
struct BIT {
int n;
vector<T> d;
BIT(int n=0):n(n),d(n+1) {}
void add(int i, T x=1) {
for (i++; i <= n; i += i&-i) {
d[i] += x;
}
}
T sum(int i) {
T x = 0;
for (i++; i; i -= i&-i) {
x += d[i];
}
return x;
}
T sum(int l, int r) {
return sum(r-1) - sum(l-1);
}
};
// Coodinate Compression
template<typename T=int>
struct CC {
bool initialized;
vector<T> xs;
CC(): initialized(false) {}
void add(T x) { xs.push_back(x);}
void init() {
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
initialized = true;
}
int operator()(T x) {
if (!initialized) init();
return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
}
T operator[](int i) {
if (!initialized) init();
return xs[i];
}
int size() {
if (!initialized) init();
return xs.size();
}
};
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<ll> s(n+1);
rep(i, n) s[i+1] = s[i]+a[i];
CC<ll> cc;
rep(i, n+1) cc.add(s[i]);
mint ans;
BIT<mint> t(n+1);
t.add(cc(s[0]));
for (int i = 1; i <= n; ++i) {
int x = cc(s[i]);
ans = t.sum(x);
t.add(x, ans);
}
cout << ans << '\n';
return 0;
}
37. 菜单设计
小爱需要从 $n$ 道菜中，选出 $m$ 道菜作为餐厅的菜单。已知第 $i$ 道菜的美味值为 $x_i$。还有 $p$ 种加分规则，第 $i$ 条规则包含三个参数 $a_i$、$b_i$ 和 $c_i$，表示在第 $a_i$ 道菜后，如果下一道菜是 $b_i$ 道，会有额外 $c_i$ 点美味值。
如何设计菜单，才能使美味值到达最大。
限制：
- $1 \leqslant m \leqslant n \leqslant 18$
- $0 \leqslant x_i, c_i \leqslant 10^9$
- $1 \leqslant a_i, b_i \leqslant n$
- $1 \leqslant p \leqslant n \times (n-1)$
算法分析
旅行商问题
记 dp[S][i] 表示已经挑选的菜的集合为 $S$，且最后一道菜挑选的是 $i$ 的最大满意度
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
inline void chmax(ll& a, ll b) { if (a < b) a = b; }
int main() {
int n, m;
cin >> n >> m;
vector<int> x(n);
rep(i, n) cin >> x[i];
int p;
cin >> p;
vector g(n, vector<int>(n));
rep(i, p) {
int a, b, c;
cin >> a >> b >> c;
--a; --b;
g[a][b] = c;
}
int n2 = 1<<n;
vector dp(n2, vector<ll>(n));
rep(i, n) dp[1<<i][i] = x[i];
rep(s, n2)rep(i, n) if (s>>i&1) {
rep(j, n) if (~s>>j&1) {
chmax(dp[s|1<<j][j], dp[s][i]+g[i][j]+x[j]);
}
}
ll ans = 0;
rep(s, n2) if (__builtin_popcount(s) == m) {
rep(i, n) chmax(ans, dp[s][i]);
}
cout << ans << '\n';
return 0;
}
38. ABC243F
抽 $K$ 次奖，其中有 $c_i$ 次抽到奖品 $i$ 的概率为 $\frac{K!}{\prod c_i!} \prod p_i^{c_i}$
固定某个 $c_i$，可以计算出关于 $i$ 的组合数，那么就可以通过以下 $\operatorname{dp}$ 来解决原问题
记 dp[x][y][z] 表示所有的非负整数序列 $(c_1, c_2, \cdots, c_x)$ 的 $\displaystyle \frac{1}{\prod\limits_{i=1}^x c_i!} \prod_{i=1}^x p_i^{c_i}$ 的总和，其中这个序列 $c$ 需要满足 $c_i \neq 0$ 的个数有 $y$ 个以及 $\displaystyle\sum_{i=1}^x c_i = z$
那么最后的答案就是 $dp[N][M][K] \times K!$
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using mint = modint998244353;
mint dp[55][55][55];
int main() {
int n, m, K;
cin >> n >> m >> K;
vector<int> w(n);
rep(i, n) cin >> w[i];
int W = reduce(w.begin(), w.end());
vector<mint> p(n);
rep(i, n) p[i] = mint(w[i])/W;
vector powp(n, vector<mint>(K+1, 1));
rep(i, n)rep(j, K) powp[i][j+1] = powp[i][j]*p[i];
vector<mint> fact(K+1, 1), ifact(K+1);
rep(i, K) fact[i+1] = fact[i]*(i+1);
ifact[K] = fact[K].inv();
for (int i = K; i > 0; --i) {
ifact[i-1] = ifact[i]*i;
}
dp[0][0][0] = 1;
rep(i, n)rep(j, n)rep(k, K+1) {
int ni = i+1;
dp[ni][j][k] += dp[i][j][k];
for (int d = 1; k+d <= K; ++d) {
int nj = j+1, nk = k+d;
mint now = powp[i][d] * ifact[d];
dp[ni][nj][nk] += dp[i][j][k]*now;
}
}
mint ans = dp[n][m][K] * fact[K];
cout << ans.val() << '\n';
return 0;
}
39. ABC234G
记 dp[i] 表示将前 $i$ 个数分割成若干段的价值总和
转移方程：
$ \displaystyle dp[i] = \sum_{j = 0}^{i-1} dp[j] \times (\max\{A_{j+1}, \cdots, A_i\} - \min\{A_{j+1}, \cdots, A_i\}) = \sum_{j = 0}^{i-1} dp[j] \times \max\{A_{j+1}, \cdots, A_i\} - \sum_{j = 0}^{i-1} dp[j] \times \min\{A_{j+1}, \cdots, A_i\} $
仅讨论 $\sum_{j = 0}^{i-1} dp[j] \times \max\{A_{j+1}, \cdots, A_i\}$
不妨将 $dp[j]$ 视为底边，$\max\{A_{j+1}, \cdots, A_i\}$ 视为高，我们只需找出以点 $i$ 为右边界的最大矩形
可以用单调栈来维护
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using mint = modint998244353;
struct R {
int h; mint w;
R(int h, mint w): h(h), w(w) {}
};
struct D {
mint tot;
stack<R> s;
D() {}
void add(int h, mint w) {
while (s.size() and s.top().h <= h) {
auto [nh, nw] = s.top();
tot -= nw*nh;
w += nw;
s.pop();
}
tot += w*h;
s.emplace(h, w);
}
};
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
D dmax, dmin;
dmax.add(a[0], 1);
dmin.add(-a[0], 1);
mint ans;
rep(i, n) {
ans = dmax.tot+dmin.tot;
if (i == n-1) break;
dmax.add(a[i+1], ans);
dmin.add(-a[i+1], ans);
}
cout << ans.val() << '\n';
return 0;
}
40. 分组问题
我们需要将 $n$ 个物品分组，划分成多少小组都是可以的，每个小组至少有一件物品。如果第 $i$ 个物品和 第 $j$ 个物品分在一组，会产生 $w_{i,j}$ 的得分（$i<j$）。请找到一种分组方案，让得分达到最大。
注意一些物品分在一组内会产生负数的分数。
限制：
- $1 \leqslant n \leqslant 16$
- $|a_{ij}| \leqslant 10^9$
算法分析
记 dp[S] 表示将集合 $S$ 中的物品进行分组得到的最高得分
转移方程：
$
\displaystyle
dp[S] = \max_{T \subset S} \{dp[S \setminus T] + d[T]\}
$，其中 d[T] 表示将集合 $T$ 中的物品都分在同一组的得分
此时，状态数为 $O(2^n)$，转移数为 $2^n$，那么总的时间复杂度为 $O(4^n)$，显然超时
实际上有一种技术可以只枚举 $S$ 的子集
for (int t = s; t; t = (t-1)&s) {// }
那么，如何求枚举的时间复杂度？
由于这个 for 循环的循环次数为 $2^{|S|}$，所以考虑遍历所有的 $S$
$ \begin{aligned} \sum_S 2^{|S|} &= \sum_{i=0}^n\sum_{|S| = i} 2^{|S|} \\\ &= \sum_{i=0}^n 2^i \cdot \#\{S \big| |S| = i\} \\\ &= \sum_{i=0}^n 2^i \cdot \binom{n}{i} \\\ &= \sum_{i=0}^n 2^i \cdot 1^{n-i} \cdot \binom{n}{i} \\\ &= (2+1)^n = 3^n \end{aligned} $
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
inline void chmax(ll& a, ll b) { if (a < b) a = b; }
int main() {
int n;
cin >> n;
vector a(n, vector<int>(n));
for (int i = 1; i < n; ++i) {
rep(j, i) {
cin >> a[i][j];
a[j][i] = a[i][j];
}
}
int n2 = 1<<n;
vector<ll> d(n2);
rep(s, n2) if (s) {
int b = s&-s;
d[s] = d[s^b];
int j = __builtin_popcount(b-1);
rep(i, n) if (s>>i&1) {
d[s] += a[i][j];
}
}
vector<ll> dp(n2);
rep(s, n2) {
dp[s] = d[s];
for (int t = s; t; t = (t-1)&s) {
chmax(dp[s], dp[s^t]+d[t]);
}
}
cout << dp.back() << '\n';
return 0;
}
41. ABC339E
给定一个序列 $A$，求满足任意相邻两项的绝对差不超过 $d$ 的子序列的最大长度。
限制：
- $1 \leqslant N \leqslant 5 \times 10^5$
- $0 \leqslant D \leqslant 5 \times 10^5$
- $1 \leqslant A_i \leqslant 5 \times 10^5$
算法分析
记 dp[i][j] 表示到第 $i$ 个数为止最后一个数选的是第 $j$ 个时的合法子序列的最大长度，这样时间复杂度就是 $O(n^2)$
考虑把 $j$ 的定义换成数值
转移方程：
$ \displaystyle dp[i][j] = \max_{j-d \leqslant k \leqslant j+d} \{dp[i-1][k]\} + 1 $
用线段树加速一下即可
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int op(int a, int b) { return max(a, b); }
int e() { return 0; }
int main() {
int n, d;
cin >> n >> d;
vector<int> a(n);
rep(i, n) cin >> a[i];
const int M = 500005;
segtree<int, op, e> dp(M);
rep(i, n) {
int l = a[i]-d, r = a[i]+d+1;
l = max(l, 0);
r = min(r, M);
int now = dp.prod(l, r) + 1;
dp.set(a[i], now);
}
int ans = dp.prod(0, M);
cout << ans << '\n';
return 0;
}
42. 掷骰子
给定一个正整数 $n$， 从数字 $1$ 开始，不断投掷一个六面骰子，将新得到的数字（骰子的点数为 $1$ 到 $6$），与原本的数字相乘，直到乘积大于等于 $n$ 为止。请问停止时等于 $n$ 的概率是多少？
限制：
- $1 \leqslant n \leqslant 10^{18}$
算法分析
注意到，如果 $N$ 中含有除了 $2, 3, 5$ 以外的素因子的话，答案显然为 0！
当 $n = 2^a \cdot 3^b \cdot 5^c$ 时，记 $f(n)$ 表示 $n$ 变成 $1$ 的概率，跑一遍记忆化搜索即可。
注意，由于这里 $1$ 不会产生贡献，即使投掷到 $1$，也可以再次投掷，所以只需考虑 $2, 3, 4, 5, 6$ 这 $5$ 个数。
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
using namespace std;
using ll = long long;
using mint = modint998244353;
unordered_map<ll, mint> memo;
mint f(ll n) {
if (n == 1) return 1;
if (memo.count(n)) return memo[n];
mint res;
for (int i = 2; i <= 6; ++i) {
if (n%i) continue;
res += f(n/i);
}
res /= 5;
return memo[n] = res;
}
int main() {
ll n;
cin >> n;
cout << f(n).val() << '\n';
return 0;
}
43. ABC228H
给定两个长度为 $n$ 的序列 $a = (a_1, a_2, \cdots, a_n)$ 以及序列 $c = (c_1, c_2, \cdots, c_n)$
你可以执行以下操作任意次：
- 选择一个整数 $i (1 \leqslant i \leqslant n)$，并花 $c_i$ 的费用给 $a_i$ 加上 $1$
在完成所有操作 后，你需要支付 $k \times x$ 的费用，其中 $k$ 表示 $a$ 中不同值的个数。
问你最少需要支付多少钱？
限制：
- $1 \leqslant n \leqslant 2 \times 10^5$
- $1 \leqslant x \leqslant 10^6$
- $1 \leqslant a_i, c_i \leqslant 10^6$
算法分析
可以先将序列 $a$ 做升序排序
然后考虑将 $a$ 做分段，同时将每一段中的数都变成其中的最大值
记 dp[i] 表示将序列 $a$ 的前 $i$ 个数做分段时的最小费用
转移方程：
$ \displaystyle dp[i] = \min_{j < i} (x + dp[j] + \sum_{k=j+1}^i (a_i-a_k)c_k) $
$ \sum (a_i-a_k)c_k = \sum a_ic_k - \sum a_kc_k $
令 $s_i = \sum_{j=0}^i c_j$，$t_i = \sum\limits_{j = 0}^i a_jc_j$
$ \sum (a_i-a_k)c_k = a_i \sum c_k - (t_i - t_j) = (s_i - s_j) - (t_i - t_j) $
于是，
$ \begin{aligned} dp[i] &= \min\limits_{j<i} ((s_i-s_j)a_i - (t_i-t_j) + x + dp[j])\\\ &= x + \min(s_ia_i - s_ja_i - t_i + t_j + dp[j])\\\ &= \min (-s_ja_i + t_j + dp[i]) + s_ia_i - t_i +x \end{aligned} $
对于 $\min (-s_ja_i + t_j + dp[i])$ 这部分
不妨令 $X = a_i$，这样就变成了 $AX + B$ 的形式
可以用 $\operatorname{CHT}$ 来加速
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
struct CHT {
deque<P> d;
void add(ll a, ll b) {
while (d.size() >= 2) {
auto [a1, b1] = d[d.size()-1];
auto [a0, b0] = d[d.size()-2];
if ((b0-b1)*(a-a1) < (b1-b)*(a1-a0)) break;
d.pop_back();
}
d.emplace_back(a, b);
}
ll get(ll x) {
while (d.size() >= 2) {
auto [a0, b0] = d[0];
auto [a1, b1] = d[1];
if (a0*x+b0 > a1*x+b1) break;
d.pop_front();
}
auto [a, b] = d[0];
return a*x+b;
}
};
int main() {
int n, X;
cin >> n >> X;
vector<P> a(n);
rep(i, n) cin >> a[i].first >> a[i].second;
sort(a.begin(), a.end());
vector<ll> s(n+1), t(n+1);
rep(i, n) s[i+1] = s[i] + a[i].second;
rep(i, n) t[i+1] = t[i] + a[i].first*a[i].second;
CHT d;
d.add(0, 0);
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ll x = a[i-1].first;
ll now = X + s[i]*x-t[i];
now -= d.get(x);
ans = now;
d.add(s[i], -t[i]-now);
}
cout << ans << '\n';
return 0;
}
44. 我们不喜欢WA
给出正整数$N$，求满足以下条件的长为 $N$ 的字符串数量。
- 只包含
A,C,W三种字符 - 不能包含
WA子串，也就是说字符A不能紧跟着W后面 - 任选一对相邻字符交换后，也不包含
WA子串
满足条件的字符串数量很大，只需要输出答案除以 $10^9+7$ 的余数。
限制：
- $3 \leqslant N \leqslant 10^5$
算法分析
按最后两位分类
用 dp[i][a][b] 表示最后两位是 ab 的长度为 $i$ 的字符串个数
题目要求以下连续三个字符不能出现
WAA、WCA、WWA、CWA
AWA、AWC、AWW、WAC
AAW、CAW、WAW
用 U[a][b][c] 表示 abc 是否合法
若 abc 是不能出现的 $11$ 种之一，那么 U[a][b][c] = 0
否则，U[a][b][c] = 1
dp的初值：
dp[2][A][W] = 0
dp[2][W][A] = 0
其他 dp[2][a][b] = 1
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
mint dp[100005][3][3];
set<string> st = {"WAA", "WCA", "WWA", "CWA", "AWA", "AWC", "AWW", "WAC", "AAW", "CAW", "WAW"};
int main() {
int n;
cin >> n;
rep(j, 3)rep(k, 3) dp[2][j][k] = 1;
dp[2][0][2] = dp[2][2][0] = 0;
string t = "ACW";
for (int i = 2; i < n; ++i)rep(a, 3)rep(b, 3)rep(c, 3) {
string s;
s += t[a];
s += t[b];
s += t[c];
if (st.count(s)) continue;
dp[i+1][b][c] += dp[i][a][b];
}
mint ans;
rep(j, 3)rep(k, 3) ans += dp[n][j][k];
cout << ans << '\n';
return 0;
}
45. P1725 琪露诺
一列格子依次编号为 $0 \sim n$，第 $i$ 个格子上有一个数 $a_i$ 。你一开始在格子 $0$，当你在格子 $i$ 时，你可以移动到 $[i+L, i+R]$ 中的任意一格。你可以移动到跳出格子为止，求经过的格子的最大权值和。
限制：
- $n \leqslant 2 \times 10^5$
算法分析
记 dp[i] 表示从 $0$ 跳到 $i$ 的最大收益
转移方程：
$ dp[i] = \max\{dp[j] + a_i\}, ~ i-R \leqslant j \leqslant i-L $
最终答案为 $\max\limits_{n-R+1 \leqslant i \leqslant n}\{dp[i]\}$
然后用单调递减的队列优化一下即可
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n, l, r;
cin >> n >> l >> r;
vector<int> a(n+1);
rep(i, n+1) cin >> a[i];
const int INF = 1001001001;
vector<int> dp(n+1, -INF);
dp[0] = 0;
int ans = -INF;
deque<int> q;
for (int i = l; i <= n; ++i) {
while (q.size() and dp[q.back()] <= dp[i-l]) q.pop_back();
q.push_back(i-l);
if (q.front() < i-r) q.pop_front();
dp[i] = dp[q.front()] + a[i];
if (i > n-r) ans = max(ans, dp[i]);
}
cout << ans << '\n';
return 0;
}
46. 倍数序列2
要求找到一个正整数序列，满足序列中所有的数不超过 $n$，序列长度为 $m$，且除了第一个数外，所有的数都能被前一个数整除（即是前一个数的倍数）。
我们想要知道这样的序列有多少个，输出所有满足要求的序列的个数，取除以 $10^9+7$ 的余数。
限制：
- $1 \leqslant n \leqslant 100$
- $1 \leqslant m \leqslant 100$
算法分析
记 dp[i][j] 表示以 $i$ 结尾长度为 $j$ 的序列的个数
可以做到 $O(mn^2)$
代码实现
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
mint dp[105][105];
int main() {
int n, m;
cin >> n >> m;
dp[1][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int k = 1; k <= i; ++k) {
if (i%k == 0) dp[i][j] += dp[k][j-1];
}
}
}
mint ans;
for (int i = 1; i <= n; ++i) {
ans += dp[i][m];
}
cout << ans << '\n';
return 0;
}
也可以用另一种递推方式做到 $O(mn\log n)$
即 $i \to i, 2i, 3i, \cdots$
代码实现
for (int j = 0; j < m; ++j) {
for (int i = 1; i <= n; ++i) {
for (int ni = i; ni <= n; ni += i) {
dp[ni][j+1] += dp[i][j];
}
}
}
47. ABC129E
以二进制形式给出一个整数 $L$ ，问有多少个非负整数对 $(a, b)$ 满足：$a+b = a \oplus b \le L$。答案对 $10^9 + 7$ 取模。
限制：
- $1 \leqslant L \leqslant 2^{100001}$
算法分析
$a + b = (a \oplus b) + (a \& b) \times 2$
那么 $a + b = a \oplus b \Leftrightarrow a \& b = 0$
记 dp[i][0] 表示到 $a+b$ 的前 $i$ 位为止，每一位上的数都和 $L$ 相同的方案数，dp[i][1] 表示到 $a+b$ 的前 $i$ 位为止，小于 $L$ 的方案数
代码实现
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using mint = modint1000000007;
mint dp[100005][2];
int main() {
string s;
cin >> s;
int n = s.size();
dp[0][0] = 1;
rep(i, n) {
{ // a+b = 0
if (s[i] == '0') {
dp[i+1][0] = dp[i][0];
dp[i+1][1] = dp[i][1];
}
else {
dp[i+1][1] = dp[i][0] + dp[i][1];
}
}
{ // a+b = 1
if (s[i] == '0') {
dp[i+1][1] += dp[i][1]*2;
}
else {
dp[i+1][0] += dp[i][0]*2;
dp[i+1][1] += dp[i][1]*2;
}
}
}
mint ans = dp[n][0] + dp[n][1];
cout << ans.val() << '\n';
return 0;
}
48. 删除一个元素
给出一个数组 $a_1,a_2,\cdots,a_n$，删除一个元素后，求它的最大子段和。（子段是指数组中连续的一段元素）
删除的元素可以由你自由选择，但是不能不删除任何元素，输出你能得到的最大的子段和。
限制：
- $2 \leqslant n \leqslant 10^5$
- $|a_i| \leqslant 10^9$
算法分析
枚举要删除的元素，最大子段和可能在这个元素前面、后面、或者跨越这个元素。对于跨越的情况，把“以前一个元素结尾的最大子段”和“以后一个元素开头的最大子段”拼起来。
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
using ll = long long;
inline void chmax(ll& x, ll y) { if (x < y) x = y; }
int main() {
int n;
cin >> n;
vector<ll> a(n+1);
rep(i, n) cin >> a[i];
const ll INF = 1e18;
vector<ll> f(n+1, -INF), g(n+2, -INF);
rep(i, n) f[i] = max(f[i-1]+a[i], a[i]);
for (int i = n; i >= 1; --i) {
g[i] = max(g[i+1]+a[i], a[i]);
}
ll ans = -INF;
rep(i, n) {
chmax(ans, f[i-1]);
chmax(ans, g[i+1]);
chmax(ans, f[i-1]+g[i+1]);
}
cout << ans << '\n';
return 0;
}
49. 火灾
小猴的房子着火了，他想从大火中带走价值尽可能多的物品，每次他只能带走一个，救出第 $i$ 个物品需要的时间是 $t_i$，价值为 $p_i$ 。
而第 $i$ 个物品将在起火后 $d_i$ 时间后被完全烧掉，这要求救出这个物品的时刻必须严格小于 $d_i$。特别的，如果 $t_i \ge d_i$，该物品无法被救出。
小猴一个接一个地救出他的物品，救出物品之间的时间忽略不计。问他能救出最多多少价值的物品？
限制：
- $1 \leqslant n \leqslant 1000$
- $1 \leqslant t_i \leqslant 20$
- $1 \leqslant d_i \leqslant 20000$
- $1 \leqslant p_i \leqslant 200$
算法分析
显然 $d$ 越小的物品要越早救，所以先按 $d$ 从小到大排序。然后用类似01背包的方法做dp即可。
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
struct event {
int t, p, d;
event(int t=0, int p=0, int d=0): t(t), p(p), d(d) {}
bool operator<(const event& o) const { return d < o.d; }
};
inline void chmax(int& x, int y) { if (x < y) x = y; }
int main() {
int n;
cin >> n;
vector<event> a(n);
rep(i, n) cin >> a[i].t >> a[i].p >> a[i].d;
sort(a.begin(), a.end());
vector<int> dp(20005);
rep(i, n) {
auto [t, p, d] = a[i];
for (int j = d-1; j >= t; --j) {
chmax(dp[j], dp[j-t]+p);
}
}
int ans = 0;
rep(j, a[n-1].d) chmax(ans, dp[j]);
cout << ans << '\n';
return 0;
}
50. 购买模型
商店里有 $n$ 个模型，编号为 $1 \sim n$，第 $i$ 个模型的尺寸为 $s_i$ 。
小猴想要购买若干个模型，他对购买的模型有以下要求：
- 编号从小到大排序后，对所有相邻的模型，后一个的编号是前一个的倍数。
- 编号从小到大排序后，对所有相邻的模型，后一个的尺寸严格大于前一个的尺寸。
我们认为只购买 $1$ 个模型也满足要求。
例如：有 $6$ 个模型，大小是 $[3,6,7,3,7,7]$，那么小猴可以买第 $1,2,6$ 个模型，它们的尺寸是 $[3,6,7]$；但是小猴不可以购买第 $1,2,3$ 个，因为编号 $3$ 不是它前一个编号 $2$ 的倍数；小猴也不可以购买第 $1,2,4$ 个，因为这三个的尺寸 $[3,6,3]$ 不是严格升序。
小猴想知道他最多可以购买多少个模型。输入包含多组数据。
限制：
- $1 \leqslant T \leqslant 10$
- $1 \leqslant n \leqslant 10^5$
- $1 \leqslant s_i \leqslant 10^9$
算法分析
一道变形的lis问题
直接用 $O(n^2)$ 算法可以解决问题，但是对较大的 $n$ 会超时。如果用类似筛法的做法，在更新状态时，用 $i$ 的状态去更新 $i$ 的倍数的状态，总复杂度会降到 $O(n\log n)$ 。
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
inline void chmax(int& x, int y) { if (x < y) x = y; }
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> s(n+1);
rep(i, n) cin >> s[i];
int ans = 0;
vector<int> dp(n+1, 1);
rep(i, n) {
for (int j = i*2; j <= n; j += i) {
if (s[j] > s[i]) chmax(dp[j], dp[i]+1);
}
chmax(ans, dp[i]);
}
cout << ans << '\n';
}
return 0;
}
51. 买一送一
高桥去一个比萨店买比萨。
店里有 $n$ 种比萨出售，第 $i$ 种的价格为 $p_i$ 元，美味度为 $d_i$。比萨店正在开业酬宾，每购买 $1$ 个比萨，就可以免费获得一个售价更小的比萨。
于是高桥君重复以下购买比萨的过程：
（1）选择一个比萨（假设是第 $i$ 种），花费 $p_i$ 元购买第ii种比萨。
（2）从价格小于 $p_i$ 元的比萨中选择一个，免费获得这个比萨。
高桥只有 $K$ 元，通过合理选择每次购买和免费获得的比萨，他最多可以得到的最大美味度的总和是多少？
限制：
- $1 \leqslant n \leqslant 300$
- $1 \leqslant K \leqslant 10000$
- $1 \leqslant p_i \leqslant K$
- $1 \leqslant d_i \leqslant 5000$
算法分析
完全背包
免费赠送的披萨一定选能选的价值最多的，所以只要先处理一下物品价值就可以了
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
int n, k;
cin >> n >> k;
vector<int> p(n), d(n);
rep(i, n) cin >> p[i] >> d[i];
vector<int> v(n);
rep(i, n) {
int maxd = 0;
rep(j, n) if (p[j] < p[i]) {
maxd = max(maxd, d[j]);
}
v[i] = d[i]+maxd;
}
vector<int> dp(k+1);
rep(i, n) {
for (int j = p[i]; j <= k; ++j) {
dp[j] = max(dp[j], dp[j-p[i]]+v[i]);
}
}
cout << dp[k] << '\n';
return 0;
}
52.魔法球
你有 $N$ 个魔法球，第 $i$ 个魔法球有一个参数 $A_i$，对一个整数施法，将会让 $X$ 变成 $X \oplus A_i$ 。
你有一个整数 $0$，可以对这个整数任意次施法，问可以得到多少个不同的整数。
限制：
- $1 \leqslant N \leqslant 5000$
- $1 \leqslant A_i \leqslant 2^{14}$
算法分析
类似背包问题， $a_i$ 对应背包问题中的物品重量
记 dp[i][j] 表示在前 $i$ 个整数中选出若干个整数施法，能否得到整数 $j$
状态转移：
- 不选 $a_i$，对应 $dp[i-1][j]$
- 选 $a_i$，对应 $dp[i-1][j \oplus a_i]$
- 以上两种情况有一个是
true，则dp[i][j]是true
边界：
dp[0][0] = true，其余的dp[0][]为false
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
const int M = 1<<15;
bool dp[M];
int main() {
int n;
cin >> n;
dp[0] = true;
rep(i, n) {
int a;
cin >> a;
rep(j, M) {
dp[j] |= dp[j^a];
}
}
int ans = 0;
rep(i, M) if (dp[i]) ans++;
cout << ans << '\n';
return 0;
}
53. 旅行
$N$ 对夫妻去旅行，分成若干组，每组至少要有一对夫妻，问一共有多少种不同的分法。由于答案可能很大，需要输出答案模 $10^9+7$ 的结果。
两种分法不同，当且仅当至少有一个组的成员不同。注意，分组是次序不相关的，例如以下两种分组的分法是相同的：$\{Aa\}\{Bb\}$ 和 $\{Bb\}\{Aa\}$
限制：
- $1 \leqslant n \leqslant 600$
算法分析
- 枚举有多少组，假设有 $i$ 组
-
枚举有多少对夫妻不分开，假设有 $j$ 对，显然 $j \geqslant i$
- 哪些夫妻不分开： $\binom{n}{j}$
- 分开的夫妻的选法：$[i \times (i-1)]^{n-j}$
- $j$ 对夫妻分成 $i$ 组的方案数，记为
dp[j][i]
那么最后的答案为 $\sum \binom{n}{j} \times dp[j][i] \times [i \times (i-1)]^{n-j}$
现在考虑 $dp[j][i]$ 怎么算
- 第 $j$ 对夫妻单独分组：$dp[j][i] \leftarrow dp[j-1][i-1]$
- 第 $j$ 对夫妻不单独分组：$dp[j][i] \leftarrow dp[j-1][i] \times i$
于是，得到转移方程：
$$ dp[j][i] = dp[j-1][i-1] + dp[j-1][i] \times i $$
初始值：
- 当 $i = 1$ 时，$dp[j][i] = 1$
事实上，$j$ 对夫妻分成 $i$ 组的方案数也叫第二类斯特林数
代码实现
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//const int mod = 998244353;
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
return mint(*this) += a;
}
mint operator-(const mint a) const {
return mint(*this) -= a;
}
mint operator*(const mint a) const {
return mint(*this) *= a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return *this *= a.inv();
}
mint operator/(const mint a) const {
return mint(*this) /= a;
}
};
istream& operator>>(istream& is, mint& a) {
return is >> a.x;
}
ostream& operator<<(ostream& os, const mint& a) {
return os << a.x;
}
struct modinv {
int n;
vector<mint> d;
modinv(): n(2), d({0,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(-d[mod%n]*(mod/n)), ++n;
return d[i];
}
mint operator[](int i) const {
return d[i];
}
} invs;
struct modfact {
int n;
vector<mint> d;
modfact(): n(2), d({1,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(d.back()*n), ++n;
return d[i];
}
mint operator[](int i) const {
return d[i];
}
} facts;
struct modfactinv {
int n;
vector<mint> d;
modfactinv(): n(2), d({1,1}) {}
mint operator()(int i) {
while (n <= i) d.push_back(d.back()*invs(n)), ++n;
return d[i];
}
mint operator[](int i) const {
return d[i];
}
} ifacts;
mint comb(int n, int k) {
if (n < k || k < 0) return 0;
return facts(n)*ifacts(k)*ifacts(n-k);
}
mint dp[605][605];
int main() {
int n;
cin >> n;
mint ans;
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; ++j) {
dp[j][i] = dp[j-1][i-1] + dp[j-1][i]*i;
mint now = 1;
now *= comb(n, j);
now *= dp[j][i];
now *= mint(i*(i-1)).pow(n-j);
ans += now;
}
}
cout << ans << '\n';
return 0;
}
54.八数和
给定 $n$，记 $g(n)$ 为满足以下条件的八元组 $(a, b, c, d, e, f, g, h)$ 的个数。
- $a+b+c+d+e+f+g+h = 6n$
- $0 \leqslant a, b, c, e, f, g, h \leqslant n$
求 $g(n)$ 。
限制：
- $n \leqslant 100$
算法分析
如果没有限制每个数字 $\leqslant n$，可用隔板法计算
记 dp[i][j] 表示前 $i$ 个数和为 $j$ 的方案数
状态转移：
- 根据第 $i$ 个数的值分类统计，得到 $dp[i][j]$ 的值
- 枚举第 $i$ 个数的值 $k$，想要让前 $i$ 个数之和为 $j$，前 $i-1$ 个数的和应该是 $j-k$，对应的方案数为 $dp[i-1][j-k]$
边界：$dp[0][0] = 1$，$dp[0][1 \sim 6n] = 0$
代码实现
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[10][610];
int main() {
int n;
cin >> n;
dp[0][0] = 1;
for (int i = 1; i <= 8; ++i) {
for (int j = 0; j <= 6*n; ++j) {
for (int k = 0; k <= min(j, n); ++k) {
dp[i][j] += dp[i-1][j-k];
}
}
}
cout << dp[8][6*n] << '\n';
return 0;
}
55. vs怪物5
Toki在和一只怪物战斗，怪物的体力是 $H$。
Toki可以使用 $N$ 种魔法，使用一次第i种魔法可以减少怪物 $A_i$ 点体力，需要消耗 $B_i$ 点魔法值。魔法的使用次数没有任何限制。
通过使用魔法，让怪物体力减少到小于等于 $0$ 点，Toki最少需要消耗多少魔法值？
限制：
- $1 \leqslant H \leqslant 10^4$
- $1 \leqslant N \leqslant 10^3$
- $1 \leqslant A_i, B_i \leqslant 10^4$
算法分析
完全背包
记 dp[i][j] 表示用前 $i$ 种魔法恰好造成 $j$ 点伤害时需要的最小魔法值
转移方程：
$ dp[i][j] = \min(dp[i-1][j], dp[i-1][j-A_i] + B_i) $
答案为对所有 $\geqslant h$ 的 $j$，求 $dp[n][j]$ 的最大值
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
inline void chmin(int& x, int y) { if (x > y) x = y; }
int main() {
int h, n;
cin >> h >> n;
const int INF = 1001001001;
vector<int> dp(h+1, INF);
dp[0] = 0;
rep(i, n) {
int a, b;
cin >> a >> b;
rep(j, h) {
int nj = min(j+a, h);
chmin(dp[nj], dp[j]+b);
}
}
cout << dp[h] << '\n';
return 0;
}
56. 点菜
高桥来吃自助餐。店里提供 $N$ 道菜，吃第 $i$ 道菜需要 $A_i$ 分钟，美味度是 $B_i$ 。
店里的规则如下：
- 每次只能点一道菜。
- 每道菜只能点一次。
- 必须把之前点的菜吃完才能点下一道菜。
- 从进店后第 $T$ 分钟开始就不能点菜了，但是还可以吃之前点好的菜。
求高桥可以吃的菜的最大美味度总和。假设高桥进店马上就点了他的第一道菜，忽略点菜上菜的时间。
限制：
- $2 \leqslant N \leqslant 3000$
- $1 \leqslant T, A_i, B_i \leqslant 3000$
算法分析
显然，在第 $T-1$ 分钟点最后一道菜最好
枚举最后一道菜 $k$，此时的最大美味度是：去掉第 $k$ 道菜后，用 $T-1$ 分钟能吃的最大美味度 $+b_k$
若对 $k=1 \sim n$ 都做 $1$ 次01背包 $O(nT)$
总时间复杂度就为 $O(nT^2)$，显然超时
可以考虑预处理出前 $k-1$ 个中取若干的最大，$k+1 \sim n$ 中取若干的最大，然后将这二者加起来即可
dp1[i][j] 表示从前 $i$ 道菜中取总时间不超过 $j$ 时能得到的最大美味度
dp2[i][j] 表示从第 $i \sim n$ 道菜中取总时间不超过 $j$ 时的最大美味度
去掉 $k$ 后，用 $T-1$ 分钟的最大美味度
对 $j = 0 \sim T-1$ 取：$dp1][k-1][j] + dp2[k+1][T-1-j]$ 的最大值
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
int a[3005], b[3005];
int dp1[3005][3005], dp2[3005][3005];
inline void chmax(int& x, int y) { if (x < y) x = y; }
int main() {
int n, t;
cin >> n >> t;
rep(i, n) cin >> a[i] >> b[i];
rep(i, n) {
for (int j = 0; j <= t; ++j) {
dp1[i][j] = dp1[i-1][j];
if (j >= a[i]) {
chmax(dp1[i][j], dp1[i-1][j-a[i]] + b[i]);
}
}
}
for (int i = n; i >= 1; --i) {
for (int j = 0; j <= t; ++j) {
dp2[i][j] = dp2[i+1][j];
if (j >= a[i]) {
chmax(dp2[i][j], dp2[i+1][j-a[i]] + b[i]);
}
}
}
int ans = 0;
rep(i, n) {
for (int j = 0; j <= t-1; ++j) {
chmax(ans, dp1[i-1][j] + dp2[i+1][t-1-j] + b[i]);
}
}
cout << ans << '\n';
return 0;
}
57. 变种走格子问题
$n$ 个格子排成 $1$ 列，从左至右编号为 $1 \sim n$。他一开始站在第1个格子上，每次只能向右走若干格。但是小猴一次可以走的格子数 $x$ 必须满足以下要求：
- 存在 $1 \leqslant i \leqslant k$，使得 $x$ 满足 $L_i \le x \le R_i$。
其中 $k$ 是一个不超过 $10$ 的正整数，$[L_1,R_1],[L_2,R_2],\cdots,[L_k,R_k]$ 由输入给出。
例如 $L_1=1,R_1=1,L_2=3,R_2=4$，那么小猴一次走的格子数只能是 $1,3,4$ 中的某个数。
问：小猴要走到第 $n$ 格，一共有多少种方法？(输出答案除以 $998244353$ 的余数)
限制：
- $2 \leqslant n \leqslant 2 \times 10^5$
- $1 \leqslant k \leqslant \min(10, n)$
- $1 \leqslant L_i \leqslant R_i \leqslant n$
- 区间 $[L_1,R_1],[L_2,R_2],\cdots,[L_k,R_k]$ 之中，任意两个区间都没有公共部分
算法分析
记 dp[i] 表示走到第 $i$ 格的走法数
$dp[1] = 1$
每次可以走 $L_1 \sim R_1, L_2 \sim R_2, \cdots, L_k \sim R_k$ 步
所以 $dp[i] = dp[i-L_1] + dp[i-(L_1+1)] + \cdots + dp[i-R_1] + \cdots + dp[i-L_k] + \cdots + dp[i-R_k]$
最坏是 $\mathcal{O}(n^2)$
注意到 $dp[i-L_j] + \cdots + dp[i-R_j]$ 下标连续，可以用前缀和预处理出来
代码实现
vector<mint> dp(n+1);
vector<mint> s(n+1);
dp[1] = s[1] = 1;
for (int i = 2; i <= n; ++i)rep(j, k) {
if (i >= l[j]) dp[i] += s[i-l[j]];
if (i >= r[j]+1) dp[i] -= s[i-r[j]-1];
s[i] = s[i-1]+dp[i];
}
58. 子集均值
给定一个长度为 $n$ 的序列 $a_1, a_2, \cdots,a_n$，请问多少种选法，能够使得选中的子集中所有元素的均值恰好为给定的正整数 $k$。
限制：
- $1 \leqslant n \leqslant 60$
- $1 \leqslant a_i, k \leqslant 100$
算法分析
注意到平均值为整数，那么选到的子集和一定是子集大小的倍数
另外，这里的 $n$ 比较小，所以可以枚举选到的个数跑 $n$ 次dp即可，类似于 ABC262D
