算法
(DP,区间DP) $O(n^3m)$
首先将环从起点处断开,然后复制一遍接在后面,这样原问题就转化成了线段型的模型。
然后从集合角度来分析状态表示和状态计算:
状态表示:
f[l][r][i]
,表示所有将a[l...r]
分割成i
部分的方案的最大乘积;g[l][r][i]
,表示所有将a[l...r]
分割成i
部分的方案的最小乘积;
状态计算:
首先考虑f[l][r][i]
如何计算,关键是寻找“集合划分的依据”,划分依据一般选取“最后一步的操作”,所以这里我们可以按最后一部分的位置来将f[l][r][i]
所表示的所有方案划分成若干类:
- 最后一段是
a[l + i - 1...r]
的所有划分方案; - 最后一段是
a[l + i...r]
的所有划分方案; - …
- 最后一段是
a[r...r]
的所有划分方案;
如果最后一段是a[k...r]
,那么这一类的最大值是 f[l][k - 1][i - 1] * sum(a[k...r])
,其中sum()
计算某一段数的和模10的余数。
f[l][r][i]
取所有类别的最大值即可。
g[l][r][i]
的计算方式类似。
最终枚举所有长度是n
的区间,取最大值/最小值即可。
时间复杂度
状态总共有 $O(n^2m)$ 个,计算每个状态需要 $O(n)$ 的计算量,因此总时间复杂度是 $O(n^3m)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110, M = 10, INF = 0x3f3f3f3f;
int n, m;
int w[N], s[N];
int f[N][N][M], g[N][N][M];
int get_mod(int x)
{
return (x % 10 + 10) % 10;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
{
cin >> w[i];
w[i + n] = w[i];
}
for (int i = 1; i <= n * 2; i ++ ) s[i] = s[i - 1] + w[i];
memset(f, 0x3f, sizeof f);
memset(g, -0x3f, sizeof g);
for (int len = 1; len <= n; len ++ )
for (int l = 1; l + len - 1 <= n * 2; l ++ )
{
int r = l + len - 1;
f[l][r][1] = g[l][r][1] = get_mod(s[r] - s[l - 1]);
for (int k = 2; k <= m; k ++ )
for (int j = l + k - 2; j < r; j ++ )
{
f[l][r][k] = min(f[l][r][k], f[l][j][k - 1] * get_mod(s[r] - s[j]));
g[l][r][k] = max(g[l][r][k], g[l][j][k - 1] * get_mod(s[r] - s[j]));
}
}
int maxv = -INF, minv = INF;
for (int i = 1; i <= n; i ++ )
{
maxv = max(maxv, g[i][i + n - 1][m]);
minv = min(minv, f[i][i + n - 1][m]);
}
cout << minv << endl;
cout << maxv << endl;
return 0;
}
一个月前就有了?
暑假在牛客网讲过20次历年题,当时把所有讲过的题目的题解都写了,现在重新在我们自己这里讲一遍~
叫数字游戏的题太多了。数位dp里也有两道数字游戏。
题目的来源太多了,这一点难以避免,所以记题目序号会好点。
还是出题人文学素养不够。题编成恨7那样,像重都难。
哈哈是的
闫老师的直播是非常严肃的直播。那么搞笑的题意,老师完全无视,直接讲题。
有时候题目背景太复杂就直接过滤掉了。
闫老师,严肃的老师。
请问请问:为什么在
for (int len = i; len <= n; len ++ )
的这一段中区间的长度是从i
开始枚举的呢???表示并不是很懂这个循环的意思,而且感觉破环为链的作用并没有体现在代码中,阅读代码之中有点蒙……提一个小小的建议:状态转移方程最好还是要写在题解中吧……(只是小小的建议,没有其他的意思。)我理解了破环为链的操作但是,还是没有理解那个循环。
嗯,我懂了!!!
上面代码中的
len
是从1
开始循环的,不是从i
开始的。破环成链是在这里进行的:for (int i = 1; i <= n * 2; i ++ ) s[i] = s[i - 1] + w[i];
。嗯嗯,非常谢谢
写的太好了
谢谢hh
666666
2333333
Y大辛苦了
最近事情确实比较多