专栏文章

题解：P1043 [NOIp 2003 普及组] 数字游戏

NNewbieZZZ
P1043题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miqgzpvq
此快照首次捕获于
2025/12/04 04:39
3 个月前
此快照最后确认于
2025/12/04 04:39
3 个月前
查看原文
你说得对，但是这是 T2。（

解法

区间 DP or 划分 DP。

前置部分

（都是小问题，相信你喵。）
首先，又是一圆圈，怎么办？当然是破环成链，把数组复制……等等，可以用队列模拟一个环！每次需要用到队首的时候，取出 Ta，再放回队尾就可以了。方便又快捷。
维护环的起点，要在每次循环后，将队首弹出再重新加入队列。
本题需要用到区间和进行得分计算，所以自然而然地想到维护前缀和。（由于我用了队列模拟环，所以代码里我直接对原数组进行原地前缀和计算，不额外使用空间。）
注：为了防止出现模运算后得到负数得分，我们可以在前缀和计算时利用模运算的性质，去除负数（显然此推论成立）：
推论 若 a≡c(modn),b≡d(modn)a\equiv c\pmod n,b \equiv d\pmod n，则 a+c≡b+d(modn)a+c \equiv b+d\pmod n 。
题中要求将总和模 1010，我们可以给原数加上一个模 1010 得 00 的较大值，如加上 10810^8：a[i] = (a[i]+100000000) % 10，这样不影响任何绝对值小于等于 10810^8 的整数的得分计算。

dp 部分

我们可以想到，这道题应该是一个区间 dp。这种 dp 一般是这样解决的：
令状态 fi,jf_{i,j} 表示将 [i,j][i,j] 的所有元素合并能获得的价值的最值，那么 fi,j=max⁡/min⁡{fi,k+fk+1,j+val}f_{i,j}=\max / \min\{f_{i,k}+f_{k+1,j}+val\}，其中 valval 为将这两组元素合并起来的价值。
但在这题中，这种状态较难设计。我们不妨直接设 dpi,jdp_{i,j} 表示将前 ii 个数分成 jj 个部分，所能达到的最大得分。（最小得分为 fi,jf_{i,j}，同理。）
这样设计状态，我们要先枚举 jj，后枚举 ii。这样才能保证无后效性。
（要开始推状态转移方程了哟。）
区间 dp 还有一个思想：枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最值，得到原问题的最值。
在这题中，我们可以将分割点设在第 j−1j-1 个区间与第 jj 个区间之间，这样可以方便递推实现。（将前面 j−1j-1 个小区间的得分先计算，再合并到第 jj 个区间）
我们可以从小数字中试图寻找普遍规律。（其中 k(1≤k<i)k(1\le k<i) 表示分割点）
dp_{i, 1} = & \max\left\{s_{i} \bmod 10\right\} \\ dp_{i, 2}=&\max\left(dp_{k, 1}\times(s_{i} - s_{k}) \bmod 10 \right)\\ dp_{i, 3}=&\max\left(dp_{k, 2}\times(s_{i} - s_{k}) \bmod 10 \right)\\ \cdots \end{aligned}$$ 我们发现，分成 $j$ 段的价值等价于分成 $j-1$ 段的价值和分割出的第 $j$ 个区间 $[k, i]$ 的价值之和。 即： $$dp_{i, j} = \max \left\{dp_{k, j-1} \times\left(s_{i} - s_{k}\right)\bmod 10 \right\}$$ $f_{i,j}$ 同理。 其实，上文的状态表示和方程，主要与划分 dp 有关。我们用区间 dp 的思想，一步一步推出了划分 dp 的一般方程（把模数去掉就是了），可以看出很多类型的 dp 之间是有内在关联的。 --- （啊，推出来了，算你厉害。但你一定忘了什么！） 首先，我们要求最大（小）得分，所以我们要把 dp 数组全部初始化为一个极小（大）值。 $1$ 段的情况怎么办？\ 只有一段，得分显然是这一段的和模 $10$ 的绝对值。即 $f_{i,1}=dp_{i,1}=|sum_i \bmod 10|$。（代码里我用了上文处理的方法） 最后，别忘了统计每次 $dp_{n, m}$ 和 $f_{n,m}$ 的最值。 ### 代码 （考察你码力的时候到了，操起键盘吧。一切伟大的思想，都有一个微不足道的开始。） ```cpp #include <bits/stdc++.h> using namespace std; #define int long long // 防人之心不可无 int dp[2025][20], a[2025], f[2025][20]; int n, m, ans = -1e9, now = 2e9; signed main(){ queue<int> q; cin >> n >> m; for(int i=1; i<=n; ++i){ cin >> a[i]; q.push(a[i]); } for(int _=1; _<=n; ++_){ // 用队列模拟要进行 n 次操作 for(int i=1; i<=n; ++i) { int x = q.front(); q.pop(); a[i] = x; // 更新数组 q.push(x); } for(int i=0; i<=n; ++i) { for(int j=0; j<=m; ++j){ dp[i][j] = -1e9, f[i][j] = 1e9; } } for(int i=1; i<=n; ++i) { a[i] += a[i-1]; // 原地前缀和 a[i] = (a[i]+1000000000) % 10; f[i][1] = dp[i][1] = (a[i]+1000000000) % 10; } for(int j=2; j<=m; ++j){ for(int i=j; i<=n; ++i){ for(int k=1; k<i; ++k){ dp[i][j] = max(dp[i][j], dp[k][j-1] * ((a[i] - a[k] + 1000000000) % 10)); f[i][j] = min(f[i][j], f[k][j-1] * ((a[i] - a[k] + 1000000000) % 10)); } // 转移 } } ans = max(ans,dp[n][m]); now = min(now, f[n][m]); // 统计答案 int x = q.front(); q.pop(); q.push(x); // 更新这个环的状态 } cout << now << '\n' << ans; return 0; } ``` 时间复杂度约为 $\Theta(n^3 m)$，空间复杂度为 $\Theta(nm)$。 （唔，写完了，懂了。赶紧给作者点个赞吧。） ### 鸣谢 感谢所有管理大大的审核。 管理员 @[Acoipp](https://www.luogu.com.cn/user/674469) 巨佬指出了本文一处概念性错误！ End.

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...