2、在本题中,
2.1 设置状态 f[L][R][K] 表示从 L 到 R 这段长度为 R - L + 1 的连续序列划分为 K 组的 最小值;
2.2 设置状态 b[L][R][K] 表示从 L 到 R 这段长度为 R - L + 1 的连续序列划分为 k 组的 最大值;
由于 划分为 K 段的最小值 ,是从 划分为 K - 1 段的最小值 转移而来。即 f[K] = f[K-1] * 末了一段数值和
注解:
如上图所示,设左区间端点是L,右区间端点是R,在L和R之间找一点 J来区分末了一段。我们枚举 J的位置。
由于:
1、L -> J 为 K - 1 段,以是 J − L + 1 ≥ K − 1 J - L + 1 ≥ K - 1 J−L+1≥K−1,以是 J ≥ L + K − 2 J ≥ L + K -2 J≥L+K−2;
2、J+1 -> R为末了1段,以是 J + 1 ≤ R J+1 ≤ R J+1≤R,以是 J ≤ R − 1 J ≤ R - 1 J≤R−1。
以是 J 的范围是 J ∈ [ L + k − 2 , R − 1 ] J ∈ [L + k - 2,R - 1] J∈[L+k−2,R−1]
以是动态转移方程为:
f [ L ] [ R ] [ K ] = m i n ( f [ L ] [ R ] [ K ] , f [ L ] [ J ] [ K − 1 ] ∗ ( a J + 1 + . . . + a R ) ) f [L][R][K] = min( f[L][R][K], f[L][J][K - 1] * (a_{J+1}+...+a_R) ) f[L][R][K]=min(f[L][R][K],f[L][J][K−1]∗(aJ+1+...+aR));
b [ L ] [ R ] [ K ] = m a x ( b [ L ] [ R ] [ K ] , b [ L ] [ J ] [ K − 1 ] ∗ ( a J + 1 + . . . + a R ) ) b [L][R][K] = max( b[L][R][K], b[L][J][K - 1] * (a_{J+1}+...+a_R) ) b[L][R][K]=max(b[L][R][K],b[L][J][K−1]∗(aJ+1+...+aR));
为了快速盘算,我们记 s[n] 为前 n 项的 前缀和 数组,则上式中的 a J + 1 + . . . + a R = s [ R ] − s [ J ] a_{J+1}+...+a_R = s[R] - s[J] aJ+1+...+aR=s[R]−s[J] 。
题解代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 10; // N = 2*n + 余量。n上限为50
const int INF = 0x3f3f3f3f; // 无穷大
const int NINF = 0xafafafaf; // 无穷小
int n, m;
int a[N], s[N]; // a[]为数值;s[]为前缀和
int f[N][N][M]; // f[L][R][K] 表示从 L 到 R 这段长度为 R - L + 1 的连续序列划分为 K 组的最小值
int b[N][N][M]; // b[L][R][K] 表示从 L 到 R 这段长度为 R - L + 1 的连续序列划分为 k 组的最大值;
int max_ans = NINF;
int min_ans = INF;
// 计算 num对 10的模。如果是负数,需转成整数
int get_mod(int num)
{
return (num % 10 + 10) % 10; // 调整负数模为非负整数
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
a[i + n] = a[i]; // 把环断开为链,然后复制一倍接在末尾
}
for(int i = 1; i <= n * 2; i ++) a[i] = get_mod(a[i]); // 计算前先对10取模
// 求前缀和
for(int i = 1; i <= n * 2; i ++) s[i] = s[i - 1] + a[i];
memset(f, 0x3f, sizeof(f)); // 将最小值初始化为无穷大
memset(b, 0xaf, sizeof(b)); // 将最大值初始化为无穷小
for(int len = 1; len <= n; len++) // 外围枚举所有用到的区间长度,从1开始
{
for(int l = 1; l + len - 1 < n * 2; l++) // 在每一个区间长度下,枚举左端点的位置