前言

当然在 上一篇 之后我还写了很多 dp 但没有收录。于是算了。

四十九也算是个好数字。

第 x+1x+1 道：Time is Mango🥭

链接：https://www.luogu.com.cn/problem/P6005

（下面这些，与其说「题解」，不如说「思考过程」更合适）

首先审题。一个有向图，每个节点有价值。使价值之和减去【「经过的边数」的平方乘以一个常数的值】最大。

数据范围，N≤1000,M≤2000N\le 1000, M\le 2000。一看就是在暗示我用 O(n2)O(n^2) 左右的算法。

样例是个正环。如果按最短路一直绕回最大化。但需要减去一个值。这个值是平方的，增长速度快于这个环。就会停下来。

我计划将状态定义为：dp[i][j] 经过了 i 条边，上一个点是 j 时赚最多的钱。

但是在样例解释中经过的边数 mallm_{all} 为 66 远大于总边数 M=3M = 3。mallm_{all} 的范围是什么？大概要看 C×T2C\times T^2。CC 最小最小只有 11。就算总权值只有 11，那么 mallT×1\dfrac{m_{all}}{T} \times 1 也要超过 C×T2C\times T^2。mallT>C×T2\dfrac{mall}{T} > C \times T^2。好像不是很好求。

算了先想状态转移方程，在过程中判断会不会超过。

for i = 1, i <= inf:
     for j = 1 to n:  # 比较「上一个点」只可能是 1~n
     # 那「这一个点」要选什么呢？
          dp[i][j] = dp[i - 1][j]。。。

难道是定义为 XXX 在不超过 C×T2C\times T^2 的情况下能走多久？但这变成 TT 最大而不是钱最多了。

话说为什么要说「上一个点是 j」呢，直接「目前走到 j」不就好了？

因此：dp[i][j]：走了 i 步到 j 点能拿到最多的钱。

for i = 1 to inf:
    for t = 1 to m: # 遍历所有 **边**
        [u, v] = edg[t]
        dp[i][v] = max(dp[i][v], dp[i - 1][u] + c_v)

不过 ii 的尽头在哪里呢？如果 dp[i][v] < c * i ^ 2，那是不是就可以结束了。

空间上也可以优化。第 i 层只涉及到 i - 1 层。所以可以用滚动数组优化。

答案的话就要枚举了。枚举 kk。取 dp[k][1] 的 max⁡\max。

第 x+2x+2 题：[NOIP 2003 提高组] 加分二叉树

链接：直接在 BCOI 或 洛谷 搜索「加分二叉树」。下面的是我在 BCOI 里我写的的题解复制的。

一个思路：枚举根节点。将根所在区间分割成两半。如果设根的区间内节点是 [l,r][l, r]，枚举到根为 kk。那么分成两半区间为 [l,k−1][l, k - 1] 和 [k+1,r][k + 1, r]。可以用区间 DP。

定义状态变量

定义 dpl,rdp_{l,r} 为子树内节点为 [l,r][l,r] 的最大价值。

状态转移方程

枚举根节点 kk（或是区间 DP 定义内的“断点”）。那么左子树（左区间）就是 [l,k−1][l,k-1]，价值是 dpl,k−1dp_{l,k-1}。右子树价值 dpk+1,rdp_{k+1,r}。根据公式，如果根为 kk，那么价值为 dpl,k−1×dpk+1,r+akdp_{l,k-1}\times dp_{k+1,r}+a_{k}。取所有根的 max⁡\max 即可。

边界

注意空子树价值为 11。在上面的转移中，l≤k≤rl\le k\le r。同时 k−1k-1 和 k+1k+1 有可能不在 [l,r][l,r] 范围内。此时那个区间就是空子树。

所以可以定义 dpi+1idp_{i+1}{i} 为空子树，即价值为 11。

叶子节点的价值就是节点的价值。所以当 l=rl=r 时，dpl,r=aldp_{l,r}=a_l。

答案

dp1,ndp_{1,n}。

前序遍历

可以额外设置一个数字 rtl,rrt_{l,r}，表示区间 [l,r][l,r] 的根为 rtl,rrt_{l,r}。然后递归遍历 [l,rtl,r−1][l, rt_{l,r}-1] 和 [rtl,r+1,r][rt_{l,r}+1,r]。

代码

代码很占位置就不放了（🌫️）

第 x+3x+3 题：[CSP-J 2024] 小木棍

贪心分讨

首先看特殊性质，分别给了 n=7k,n=7k+1n=7k,n=7k+1。那么其实可以推出 7k+2,7k+3,...,7k+67k+2,7k+3,...,7k+6。

然后写个暴力乱搞能求出 5050 以内数字的结果就能找出规律了。

暴力 
bool lest(string a, string b)
{ // a < b ?
	if (a.size() != b.size()) return a.size() < b.size();
	return a < b;
}

void dfs(string k, int sum)
{
	if (sum > mxn) return ;
	if (st.count(sum) && lest(st[sum], k))
		return;
	st[sum] = k;
	
	for (char i = '0'; i <= '9'; ++i)
	{
		if (sum == 0 && i == '0') continue;
		dfs(k + i, sum + skk[i - '0']);
	}
}

然后手玩几个数据：

  1. 1→−1,2→1,3→7,...,6→61\to-1,2\to1,3\to7,...,6\to6；
  2. 7→8,14→88,21→8887\to8,14\to88,21\to888；
  3. 8→10,15→108,22→10888\to10,15\to108,22\to1088；
  4. 9→18,16→188,23→18889\to18,16\to188,23\to1888；
  5. 10→22,17→200,24→200810\to22,17\to200,24\to2008；
  6. 11→20,18→2...11\to20,18\to2...

算了，自己手算几个样例可得：

贪心分类讨论 
void solu()
{
	cin >> n;
	
	// n <= 1   -> -1
	if (n < 7)
	{
		if (n <= 1) cout << -1;
		if (n == 2) cout << 1;
		if (n == 3) cout << 7;
		if (n == 4) cout << 4;
		if (n == 5) cout << 2;
		if (n == 6) cout << 6;
	}
	// n = 7k   ->  88...88(k)
	else if (n % 7 == 0)
	{
		for (int i = 1; i <= (n / 7); ++i)
			cout << 8;
	}
	// n = 7k + 1  -> 10 + 88...88
	else if (n % 7 == 1)
	{
		cout << 10;
		n -= 8;
		for (int i = 1; i <= (n / 7); ++i)
			cout << 8;
	}
	// n = 7k + 2   ->  1 + 88...88
	else if (n % 7 == 2)
	{
		cout << 1;
		n -= 2;
		for (int i = 1; i <= (n / 7); ++i)
			cout << 8;
	}
	// n = 7k + 3  ->   200 + 88...88
	else if (n % 7 == 3)
	{
		if (n == 10) cout << 22; // 10 -> 22
		else
		{
			cout << 200;
			n -= 17;
			for (int i = 1; i <= (n / 7); ++i)
				cout << 8;
		}
	}
	// n = 7k + 4  -> 20 + 88...88
	else if (n % 7 == 4)
	{
		cout << 20;
		n -= 11;
		for (int i = 1; i <= (n / 7); ++i)
			cout << 8;
	}
	// n = 7k + 5   -> 2 + 88...88
	else if (n % 7 == 5)
	{
		cout << 2;
		n -= 5;
		for (int i = 1; i <= (n / 7); ++i)
			cout << 8;
	}
	// n = 7k + 6    -> 6 + 88...88
	else
	{
		cout << 6;
		n -= 6;
		for (int i = 1; i <= (n / 7); ++i)
			cout << 8;
	}
	cout << '\n';
}

时间复杂度是 O(Tlog⁡7n)O(T\log_7 n)。

动态规划

定义 dpidp_i 表示 ii 根木棍能拼出的最小数字。转移：设最后一个数字是 jj。拼出 jj 的木棍数是 dd。那么可以用 dpi−d+jdp_{i-d}+j（此处加法表示拼接）更新 dpidp_{i}。即 dpi=min⁡(dpi,dpi−d+j)dp_i=\min(dp_i,dp_{i-d}+j)。答案就是 dpndp_{n}。dpdp 是不会变的。可以一开始读入所有 nn。对最大的 nn 进行 DP。

时间复杂度 O(Tn)O(Tn)。前提是拼接的时间是 O(1)O(1)。DP 比较简单。问题在于如何表示答案。

答案可能很大。n≤105n\le 10^5，答案可能有 1050010^{500}。所以不能用 int 或 long long 甚至 int_128 存。

字符串

dxd 说用字符串。

只要不超空间，字符串能表示非常长的数字。但字符串赋值的时间复杂度是 O(n)O(n)。也就是说，如果 dp 用字符串存，时间会退化为 O(Tn2)O(Tn^2)。

字符串 50 分 TLE 
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

using ll = long long;

string min_string(string a, string b) {
	if (a.size() != b.size()) {
		return a.size() < b.size() ? a : b;
	} else {
		return a < b ? a : b;
	}
}

int main() {
	freopen("sticks.in", "r", stdin);
	freopen("sticks.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, max_n = 0;
	cin >> n;
	vector <int> a(n + 1, 0);
	vector <int> number_size{6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		max_n = max(max_n, a[i]);
	}

	vector <string> ans(n + 1, "0"); // 记录答案
	// dp 使用滚动数组避免 MLE
	vector <string> dp{"-1", "-1", "1", "7", "4", "2", "6", "8"};
	for (int i = 1; i <= 7; ++i) { // a 中可能包含 dp 初值
		for (int j = 1; j <= n; ++j) { // 记录答案
			if (a[j] == i) {
				ans[j] = dp[i];
			}
		}
	}
	
	for (int i = 8; i <= max_n; i++) {
		int from = i - number_size[0];
		dp[i % 8] = dp[from % 8] + '0'; // 避免原有内容污染

		for (int j = 1; j <= 9; ++j) {
			int from = i - number_size[j];
			dp[i % 8] = min_string(dp[i % 8], dp[from % 8] + char(j + '0'));
		}

		for (int j = 1; j <= n; ++j) { // 记录答案
			if (a[j] == i) {
				ans[j] = dp[i % 8];
			}
		}
	}

	for (int i = 1; i <= n; ++i) {
		cout << ans[i] << '\n';
	}
	return 0;
}

结构体

考场为了 BFS 瞎写的结构体：

struct fu
{
	bool nos; // 不能拼
	int num[10]; // 0~9 的数量
};

输出的时候，如果 nos 为真，直接输出 −1-1。

然后在 num 找到除 00 之外最小的数。先输出这个数。然后再把除这个数之外的数字（包括 00）都输出。可以避免前导零。

关键在于比较。看看字符串是怎么比较的：

  1. 长度短的数小。
  2. 从高位往低位比。高位小的数字更小。

对于这个结构体：

位数自然就是 [0,9][0,9] 数量之和。

高位到低位可以参考输出逻辑。首先找 00 之外最小的数输出，然后依次输出。那么从高位到低位就是 最小的数字 → 0,1,...,90,1,...,9。所以可以：

  1. 先比较最小的数字。最小的数字小的数小。剩下的最小的数字相同。
  2. 比较 00 的数量。00 数量多的数字小。
  3. 比较 11 的数量。……
结构体 
#include <iostream>
#include <algorithm>
using namespace std;

using ll = long long;
const int N = 1e5 + 5;

int n, a[N], m;
int skk[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};

struct fu
{
	bool nos; // -1
	int num[10]; // 0~9 数量
}dp[8], ans[N];
// dp: 以 i 根木棍拼出的最小数字
// ans: 记录 i 的答案

fu minf(const fu & A, const fu & B)
{
	int sA = A.num[0] + A.num[1] + A.num[2]
		   + A.num[7] + A.num[8] + A.num[3]
		   + A.num[6] + A.num[5] + A.num[4]
		   + A.num[9];
	int sB = B.num[0] + B.num[1] + B.num[2]
		   + B.num[7] + B.num[8] + B.num[3]
		   + B.num[6] + B.num[5] + B.num[4]
		   + B.num[9];

	if (A.nos && !B.nos) return B;
	if (B.nos && !A.nos) return A;
	
	if (sA != sB) return (sA < sB ? A : B);
	else
	{
		int flA = 0, flB = 0;
		for (int i = 1; i <= 9; ++i)
		{
			if (A.num[i] && !flA) flA = i;
			if (B.num[i] && !flB) flB = i;
			if (flA && flB) break;
		}
		if (flA != flB) return (flA < flB ? A : B);
		if (A.num[0] != B.num[0])
			return (A.num[0] > B.num[0] ? A : B);
		for (int i = 1; i <= 9; ++i)
		{
			if (i == flA) continue;
			if (A.num[i] != B.num[i])
				return (A.num[i] > B.num[i] ? A : B);
		}
	}
	return A;
}

fu FU_MAX()
{
	return {1, {10000, 1111, 
		2222, 3333, 4444, 5555, 
		6666, 7777, 8888, 9999}};
}

void print(fu & f)
{
	if (f.nos)
	{
		cout << "-1\n";
		return ;
	}

	f.num[2] += f.num[3];
	f.num[3] = 0;

	int flag = -1;
	for (int i = 1; i <= 9; ++i)
	{
		if (f.num[i])
		{
			flag = i;
			for (int j = 1; j <= f.num[i]; ++j)
				cout << i;
			break;
		}
	}
	for (int i = 0; i <= 9; ++i)
	{
		if (i == flag) continue;
		for (int j = 1; j <= f.num[i]; ++j)
			cout << i;
	}
	cout << '\n';
}

int main() 
{
	freopen("sticks.in", "r", stdin);
	freopen("sticks.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		m = max(m, a[i]);
	}

	// dp 初值
	dp[0] = {1, {0}};
	dp[1] = {1, {0}};
	//           0  1  2  3  4  5  6  7  8  9
	dp[2] = {0, {0, 1, 0, 0, 0, 0, 0, 0, 0, 0}};
	dp[3] = {0, {0, 0, 0, 0, 0, 0, 0, 1, 0, 0}};
	dp[4] = {0, {0, 0, 0, 0, 1, 0, 0, 0, 0, 0}};
	dp[5] = {0, {0, 0, 1, 0, 0, 0, 0, 0, 0, 0}};
	dp[6] = {0, {0, 0, 0, 0, 0, 0, 1, 0, 0, 0}};
	dp[7] = {0, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0}};

	for (int i = 1; i <= 7; ++i)
		for (int j = 1; j <= n; ++j)
			if (a[j] == i) ans[j] = dp[i];

	for (int i = 8; i <= m; ++i)
	{
		dp[i % 8] = FU_MAX();
		for (int j = 0; j <= 9; ++j)
		{
			int t = (i - skk[j]) % 8;
			fu dt = dp[t];
			++dt.num[j];
			dp[i % 8] = minf(dp[i % 8], dt);
		}

		for (int j = 1; j <= n; ++j)
		{
			if (a[j] == i)
				ans[j] = dp[i % 8];
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		print(ans[i]);
	}
	return 0;
}

第 x+4x+4 题：[CSP-J2019] 纪念品

可以先从 T=2T=2 考虑。

例如样例里这样行：

P1=10,20,15P2=15,17,13P_1={10,20,15} \\ P_2={15,17,13}

如果买入 11 物品并卖出去，那么价值是 P2−P1=5P_2-P_1=5。代价是 P1P_1。背包容量是金币数量 mm。以此进行完全背包，新得出的最大价值即为利益。利益加上原有钱就是新的金币数量。

第 x+5x+5 题：[CSP-J2020] 方格取数

定义 upi,jup_{i,j} 表示走到 (i,j)(i,j) 并且第 jj 列是从下往上走的。

定义 dni,jdn_{i,j} 表示走到 (i,j)(i,j) 并且第 jj 列是从上往下走的。

转移：

  • dni,jdn_{i,j}：可以从前一列过来。前一列的位置是 (i−1,j)(i-1,j)。最大值是分别求从上往下和从下往上的最大值即 max⁡(upi−1,j,dni−1,j)\max(up_{i-1,j},dn_{i-1,j})。也可以从上面下来，即 dni,j−1dn_{i,j-1}。然后要加上当前格子的价值。
  • upi,jup_{i,j} 同理。不过 upi,jup_{i,j} 是从下面上来。所以枚举行的时候要倒序。

边界：

  1. 第一列只能从上往下走。但是最后一列要取最大值因为可以从左边过来。

答案：如上面所说，要取最大值。

第 x+6x+6 题：分组背包模板

这题看似模板，其实真的是模板 是 dxd 拿来给我们 CSP 模拟的我当时竟然没有写出来

BCOI 搜索 年货采购。

首先可以定义 dpi,jdp_{i,j} 表示选了前 ii 组，恰好花费 jj 元的方案数。

初始化，dp0,0=1dp_{0,0}=1 因为什么都不做的方案。不然后面不能转移。

转移。枚举 i,ji,j。第 ii 组没有选，枚举第 ii 组内选择第 kk 个物品，价值是 ci,kc_{i,k}。就可以从 dpi−1,j−ci,kdp_{i-1,j-c_{i,k}} 转移。注意第 ii 类物品可以不选，此时价值等于 dpi−1,jdp_{i-1,j}。

答案即 dpn,Wdp_{n,W}。

注意点

这题是模板所以很简单。但有一些坑。

  1. 不能只定义一维价值 jj，不然会有很多重复（或者可以，毕竟只涉及到 ii 和 i−1i-1）
  2. 一定要考虑第 ii 类可以不选这种情况。不然你会本来已经写出 dp 基本完整的代码但乱打对拍和 dfs 暴力代码甚至 dfs 都考虑了不选物品发现错了调半天都不知道错在哪只好写个 dfs 水个 50 分别问我怎么知道的。。。
  3. 如果你第二步成功了，那1这一步其实也不需要。样例是水的。如果没有 dpi,j=dpi−1,jdp_{i,j}=dp_{i-1,j}，统计答案时直 ∑i=1ndpi,W\sum_{i=1}^{n} dp_{i,W} 样例可过但随便弄个数据就会 hack 掉。
  4. 重要的事情说三遍，一定要考虑 ii 不选这种边界/特殊情况！！！
  1. Language
  2. 兼容模式
  3. 主题
  2. 粤ICP备2022142345号-1
  4. Worker 0, 81ms
  5. Powered by Hydro v5.0.7 Community