2022 csp-j 复赛真题

对于 $10 \%$ 的数据，保证 $b = 1$ 。
对于 $30 \%$ 的数据，保证 $b \le 2$ 。
对于 $60 \%$ 的数据，保证 $b \le 30$ ， $a^b \le {10}^{18}$ 。
对于 $100 \%$ 的数据，保证 $1 \le a, b \le {10}^9$ 。

$\text{upd 2022.11.14}$ ：新增加一组 $\text{Hack}$ 数据。

解析

题目描述

给定两个整数 (a) 和 (b)，要求计算 (a^b) 的值。如果结果大于 (10^9)，则输出 (-1)。

解题思路

由于直接使用 pow 函数可能会出现溢出问题，导致结果变为负数，无法判断是否超过了 (10^9)。因此，我们可以模拟乘方运算的过程，通过逐次累乘来计算 (a^b)：

每次将 (a) 累乘 (b) 次。如果在某次累乘时结果已经超过了 (10^9)，则可以直接输出 (-1)，并结束程序。
如果累乘完 (b) 次后结果未超过 (10^9)，则输出最终的计算结果。

优化

对于不同的 (a) 值有一些特殊情况需要考虑：

当 (a > 1) 时，累乘 (b) 次最多只需要进行 31 次循环（因为 (2^{31} \approx 10^9)），因此不会出现超时问题。
但当 (a = 1) 时，累乘 (b) 次的结果始终为 1。此时，如果 (b) 特别大，可能会执行 (b) 次循环，最坏情况下会执行 (10^9) 次，导致超时。因此可以加一个特殊判断，当 (a = 1) 时，直接输出 1，这样可以避免超时风险。

代码实现

#include<bits/stdc++.h>
using namespace std;
long long a, b, c = 1;  // c 记录乘积

int main() {
    scanf("%lld%lld", &a, &b);  // 输入 a 和 b
    if (a == 1) {  // 特殊情况，a = 1 时直接输出 1
        cout << 1;
        return 0;
    }
    
    for (int i = 1; i <= b; i++) {  // 模拟累乘
        c *= a;  // 每次累乘 a
        if (c > (long long)1e9) {  // 如果结果超过 10^9，输出 -1
            printf("-1");
            return 0;
        }
    }
    
    printf("%lld", c);  // 最后输出累乘结果
}

代码解析

输入处理：使用 scanf 读取两个整数 (a) 和 (b)。
特殊判断 (a = 1)：如果 (a = 1)，则直接输出结果为 1，因为 (1^b = 1) 对任何 (b) 都成立。
循环累乘：对于 (a > 1)，通过循环将 (a) 累乘 (b) 次。如果在累乘过程中发现结果已经大于 (10^9)，则输出 (-1) 并提前结束程序。
输出结果：如果累乘结束且结果未超过 (10^9)，则输出最终的乘积。

时间复杂度分析

当 (a > 1) 时，最多进行 31 次累乘，因为 (2^{31} \approx 10^9)。这种情况下的时间复杂度为 (O(b))。
当 (a = 1) 时，通过特判直接输出结果，避免执行过多次循环，因此没有超时风险。

[CSP-J 2022] 解密

题目描述

给定一个正整数 $k$ ，有 $k$ 次询问，每次给定三个正整数 $n_i, e_i, d_i$ ，求两个正整数 $p_i, q_i$ ，使 $n_i = p_i \times q_i$ 、 $e_i \times d_i = (p_i - 1)(q_i - 1) + 1$ 。

输入格式

第一行一个正整数 $k$ ，表示有 $k$ 次询问。

接下来 $k$ 行，第 $i$ 行三个正整数 $n_i, d_i, e_i$ 。

输出格式

输出 $k$ 行，每行两个正整数 $p_i, q_i$ 表示答案。

为使输出统一，你应当保证 $p_i \leq q_i$ 。

如果无解，请输出 NO。

样例 #1

样例输入 #1

样例输出 #1

2 385
NO
NO
NO
11 78
3 241
2 286
NO
NO
6 88

提示

【样例 #2】

见附件中的 decode/decode2.in 与 decode/decode2.ans。

【样例 #3】

见附件中的 decode/decode3.in 与 decode/decode3.ans。

【样例 #4】

见附件中的 decode/decode4.in 与 decode/decode4.ans。

【数据范围】

以下记 $m = n - e \times d + 2$ 。

保证对于 $100\%$ 的数据， $1 \leq k \leq {10}^5$ ，对于任意的 $1 \leq i \leq k$ ， $1 \leq n_i \leq {10}^{18}$ ， $1 \leq e_i \times d_i \leq {10}^{18}$ ， $1 \leq m \leq {10}^9$ 。

测试点编号	$k \leq$	$n \leq$	$m \leq$	特殊性质
$1$	$10^3$	$10^3$	$10^3$	保证有解
$2$	$10^3$	$10^3$	$10^3$	无
$3$	$10^3$	$10^9$	$6\times 10^4$	保证有解
$4$	$10^3$	$10^9$	$6\times 10^4$	无
$5$	$10^3$	$10^9$	$10^9$	保证有解
$6$	$10^3$	$10^9$	$10^9$	无
$7$	$10^5$	$10^{18}$	$10^9$	保证若有解则 $p=q$
$8$	$10^5$	$10^{18}$	$10^9$	保证有解
$9$	$10^5$	$10^{18}$	$10^9$	无
$10$	$10^5$	$10^{18}$	$10^9$	无

解析

前置知识

本题的数学基础包括整式的加减乘除。我们需要运用这些基础知识来解题，例如完全平方和与完全平方差公式等。

思路

我们首先对给出的公式进行化简：

$ed = (p-1)(q-1) + 1$

将其展开得：

$ed = pq - p - q + 1 + 1$

化简后得到：

$ed = n - p - q + 2$ （其中 $n = pq$ ）。

接着，将公式进一步整理得：

$p + q = n - ed + 2$ 。

插句闲话

看到题目中的数据范围提示“以下记 $m = n - ed + 2$ ”时，我们可以发现这正是化简后的 $p + q$ ，这说明我们的解法是正确的。

继续解题

现在我们已知以下两个等式：

\begin{cases} p + q = n - ed + 2 \\ pq = n \end{cases}

需要求出 $p$ 和 $q$ 。我们知道，如果能求出 $p - q$ ，那么问题就迎刃而解了。这里，我们复习一下初中的完全平方和与完全平方差公式。

完全平方和：((a + b)^2 = a^2 + 2ab + b^2)
完全平方差：((a - b)^2 = a^2 - 2ab + b^2)

已知 $ab = pq$ 和 $a + b = p + q$ ，我们可以通过这两个公式的差值来求出 $a - b = p - q$ 。

将完全平方和与完全平方差相减：

(a+b)^2 - (a-b)^2 = 4ab

我们可以将其整理为：

(a-b)^2 = (a+b)^2 - 4ab

于是：

a - b = \pm \sqrt{(a+b)^2 - 4ab}

代入已知的 $a+b = p+q$ 和 $ab = pq$ 即可求出 $p - q$ 。

补充解释

在这道题中，我们假设 $p$ 是较大的数， $q$ 是较小的数，因此 $p - q$ 取正值。

将 $n = pq$ 和 $p + q = n - ed + 2$ 代入可得：

\begin{cases} p + q = n - ed + 2 \\ p - q = \sqrt{(n - ed + 2)^2 - 4n} \end{cases}

我们将两个等式相加，得到：

2p = (n - ed + 2) + \sqrt{(n - ed + 2)^2 - 4n}

将等式两边同时除以 2，得到：

p = \frac{n - ed + 2 + \sqrt{(n - ed + 2)^2 - 4n}}{2}

再通过 $p + q = n - ed + 2$ 求出：

q = (n - ed + 2) - p

最终， $p$ 和 $q$ 的表达式为：

\begin{cases} p = \frac{n - ed + 2 + \sqrt{(n - ed + 2)^2 - 4n}}{2} \\ q = \frac{n - ed + 2 - \sqrt{(n - ed + 2)^2 - 4n}}{2} \end{cases}

特殊情况处理

根据题目要求， $p$ 和 $q$ 需要为正整数。如果平方根不是整数，说明 $p$ 和 $q$ 的解不符合题意，需要进行特殊处理。具体来说，我们可以利用 long long 强制转换，舍弃小数部分，并检验是否符合题目中的方程。对于无法开平方的负数，sqrt 函数返回 NaN，此时我们同样处理为无效解。

代码实现

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int main(int argc, const char * argv[]) {
    long long k;
    scanf("%lld", &k);
    while (k--) {
        long long n, e, d;
        scanf("%lld%lld%lld", &n, &e, &d);
        long long PsubQ = sqrt((n - e * d + 2) * (n - e * d + 2) - (n * 4));
        long long PaddQ = n - e * d + 2;
        long long P = (PsubQ + PaddQ) / 2;
        long long Q = PaddQ - P;
        if (P * Q == n && e * d == (P - 1) * (Q - 1) + 1 && P && Q) {
            printf("%lld %lld\n", min(P, Q), max(P, Q));
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

代码解析

输入处理：每次读取三个数 $n$ 、 $e$ 、 $d$ 。
计算 p 和 q：
- 首先通过平方差公式计算 $PsubQ = \sqrt{(n - ed + 2)^2 - 4n}$ 。
- 然后计算 $p$ 和 $q$ 。
验证条件：
- 判断 $p$ 和 $q$ 是否满足 $pq = n$ 且 $ed = (p-1)(q-1) + 1$ 。
- 如果条件满足，输出 $p$ 和 $q$ 的较小和较大值，否则输出 “NO”。
复杂度分析：每次运算时间复杂度为 $O(1)$ ，总时间复杂度为 $O(k)$ ，其中 $k$ 为询问的次数。

[CSP-J 2022] 逻辑表达式

题目描述

逻辑表达式是计算机科学中的重要概念和工具，包含逻辑值、逻辑运算、逻辑运算优先级等内容。

在一个逻辑表达式中，元素的值只有两种可能： $0$ （表示假）和 $1$ （表示真）。元素之间有多种可能的逻辑运算，本题中只需考虑如下两种：“与”（符号为 &）和“或”（符号为 |）。其运算规则如下：

$0 \mathbin{\&} 0 = 0 \mathbin{\&} 1 = 1 \mathbin{\&} 0 = 0$ ， $1 \mathbin{\&} 1 = 1$ ；
$0 \mathbin{|} 0 = 0$ ， $0 \mathbin{|} 1 = 1 \mathbin{|} 0 = 1 \mathbin{|} 1 = 1$ 。

在一个逻辑表达式中还可能有括号。规定在运算时，括号内的部分先运算；两种运算并列时，& 运算优先于 | 运算；同种运算并列时，从左向右运算。

比如，表达式 0|1&0 的运算顺序等同于 0|(1&0)；表达式 0&1&0|1 的运算顺序等同于 ((0&1)&0)|1。

此外，在 C++ 等语言的有些编译器中，对逻辑表达式的计算会采用一种“短路”的策略：在形如 a&b 的逻辑表达式中，会先计算 a 部分的值，如果 $a = 0$ ，那么整个逻辑表达式的值就一定为 $0$ ，故无需再计算 b 部分的值；同理，在形如 a|b 的逻辑表达式中，会先计算 a 部分的值，如果 $a = 1$ ，那么整个逻辑表达式的值就一定为 $1$ ，无需再计算 b 部分的值。

现在给你一个逻辑表达式，你需要计算出它的值，并且统计出在计算过程中，两种类型的“短路”各出现了多少次。需要注意的是，如果某处“短路”包含在更外层被“短路”的部分内则不被统计，如表达式 1|(0&1) 中，尽管 0&1 是一处“短路”，但由于外层的 1|(0&1) 本身就是一处“短路”，无需再计算 0&1 部分的值，因此不应当把这里的 0&1 计入一处“短路”。

输入格式

输入共一行，一个非空字符串 $s$ 表示待计算的逻辑表达式。

输出格式

输出共两行，第一行输出一个字符 0 或 1，表示这个逻辑表达式的值；第二行输出两个非负整数，分别表示计算上述逻辑表达式的过程中，形如 a&b 和 a|b 的“短路”各出现了多少次。

样例 #1

样例输入 #1

0&(1|0)|(1|1|1&0)

样例输出 #1

1
1 2

样例 #2

样例输入 #2

(0|1&0|1|1|(1|1))&(0&1&(1|0)|0|1|0)&0

样例输出 #2

0
2 3

提示

【样例解释 #1】

该逻辑表达式的计算过程如下，每一行的注释表示上一行计算的过程：

0&(1|0)|(1|1|1&0)
=(0&(1|0))|((1|1)|(1&0)) //用括号标明计算顺序
=0|((1|1)|(1&0))   //先计算最左侧的 &，是一次形如 a&b 的“短路”
=0|(1|(1&0))       //再计算中间的 |，是一次形如 a|b 的“短路”
=0|1               //再计算中间的 |，是一次形如 a|b 的“短路”
=1

【样例 #3】

见附件中的 expr/expr3.in 与 expr/expr3.ans。

【样例 #4】

见附件中的 expr/expr4.in 与 expr/expr4.ans。

【数据范围】

设 $\lvert s \rvert$ 为字符串 $s$ 的长度。

对于所有数据， $1 \le \lvert s \rvert \le {10}^6$ 。保证 $s$ 中仅含有字符 0、1、&、|、(、) 且是一个符合规范的逻辑表达式。保证输入字符串的开头、中间和结尾均无额外的空格。保证 $s$ 中没有重复的括号嵌套（即没有形如 ((a)) 形式的子串，其中 a 是符合规范的逻辑表达式）。

测试点编号	$\lvert s \rvert \le$	特殊条件
$1 \sim 2$	$3$	无
$3 \sim 4$	$5$	无
$5$	$2000$	1
$6$	$2000$	2
$7$	$2000$	3
$8 \sim 10$	$2000$	无
$11 \sim 12$	${10}^6$	1
$13 \sim 14$	${10}^6$	2
$15 \sim 17$	${10}^6$	3
$18 \sim 20$	${10}^6$	无

其中：
特殊性质 1 为：保证 $s$ 中没有字符 &。
特殊性质 2 为：保证 $s$ 中没有字符 |。
特殊性质 3 为：保证 $s$ 中没有字符 ( 和 )。

【提示】

以下给出一个“符合规范的逻辑表达式”的形式化定义：

字符串 0 和 1 是符合规范的；
如果字符串 s 是符合规范的，且 s 不是形如 (t) 的字符串（其中 t 是符合规范的），那么字符串 (s) 也是符合规范的；
如果字符串 a 和 b 均是符合规范的，那么字符串 a&b、a|b 均是符合规范的；
所有符合规范的逻辑表达式均可由以上方法生成。

解析

题目背景

这道题的解法大多数人会选择通过表达式求值来解决，但实际上可以有更简单的做法：通过从左到右顺序扫描表达式，直接求解。

解题思路

主要逻辑：我们需要明确哪些部分的表达式不会对最终结果产生贡献，以及如何跳过这些部分。

跳过无效部分：
- 如果遇到 0&，则接下来的部分只有在出现 | 或与 0& 前面匹配的 ) 时，才会对结果产生贡献，且前面的部分结果为 0。
- 如果遇到 1|，则直到遇到 | 或与 1| 前面匹配的 ) 时，才会对结果产生贡献。
优先级问题：
- 事实上，运算符的优先级并不会影响结果。比如遇到 1| 时，它会直接跳到后面的括号，因此优先级实际上是隐含的。
- 如果是 0|，它不会对结果有任何影响，& 运算同理。

举个例子：

对于表达式 0&(1|0)|(1|1|1&0)：

遇到 0&，则我们可以跳到 0&(1|0)|，因为第一个 | 在括号内，可以忽略，此时表达式变为 0|(1|1|1&0)。
由于 0| 不会对结果产生贡献，表达式简化为 (1|1|1&0)，然后再从括号开始计算。

代码解析

以下是该思路的代码实现：

#include <bits/stdc++.h>
using namespace std;

bool st;  // 暂时未使用的变量，可能用于调试
string str;  // 输入的表达式字符串
bool val;  // 表达式的最终值
int ans1, ans2, off;  // ans1 记录跳过的 & 操作数，ans2 记录跳过的 | 操作数，off 用于判断是否跳过 0& 或 1|，0 表示不用跳过
bool ed;  // 暂时未使用的变量，可能用于调试

int main(){
    ios::sync_with_stdio(false);  // 优化输入输出速度
    cin.tie(nullptr);  // 解除 cin 和 cout 的绑定
    cout.tie(nullptr);  // 解除 cin 和 cout 的绑定

    cin >> str;  // 输入表达式字符串

    for(int i = 0; i < str.size(); i++){
        if (off) {  // 如果需要跳过某些部分
            if (str[i] == '(') {  // 跳过括号内部的内容
                int x = 1;
                while (x) {
                    i++;
                    if (str[i] == '(') x++;  // 遇到 '(' 增加计数
                    if (str[i] == ')') x--;  // 遇到 ')' 减少计数
                }
            } else if (off == 1 && str[i] == '|') {
                off = 0;  // 遇到 '|' 时结束跳过
            } else if (str[i] == ')') {
                off = 0;  // 遇到括号结束
            } else if (off == 1 && str[i] == '&') {
                ans1++;  // 记录多余的 & 运算符
            } else if (off == 2 && str[i] == '|') {
                ans2++;  // 记录多余的 | 运算符
            }
        } else {  // 正常计算
            if (str[i] == '1') val = 1;  // 当前值为 1
            if (str[i] == '0') val = 0;  // 当前值为 0
            if (str[i] == '&' && val == 0) {  // 如果遇到 '0&'，则后面部分不会产生贡献
                off = 1;  // 标记跳过
                ans1++;  // 记录跳过的 & 次数
            }
            if (str[i] == '|' && val == 1) {  // 如果遇到 '1|'，则后面部分不会产生贡献
                off = 2;  // 标记跳过
                ans2++;  // 记录跳过的 | 次数
            } 
        }
    }

    cout << val << endl << ans1 << ' ' << ans2 << endl;  // 输出表达式结果及跳过的 & 和 | 次数

    return 0;
}

代码讲解

输入处理：首先读取表达式的输入字符串 str。
核心逻辑：
- 跳过部分表达式：通过变量 off 控制是否跳过部分运算符。如果遇到 0&，则接下来的部分直到出现 | 或与其匹配的 ) 才会对结果产生影响；如果遇到 1|，则类似地跳过部分直到匹配。
- 运算符处理：若 off == 1 且当前字符是 &，或者 off == 2 且当前字符是 |，则分别记录跳过的 & 和 | 次数。
结果输出：输出最终表达式的值 val，以及跳过的 & 运算符次数 ans1 和 | 运算符次数 ans2。

总结

这种解法通过顺序扫描表达式并跳过无效部分，避免了复杂的表达式求值过程，达到了简化计算的目的。

[CSP-J 2022] 上升点列

题目描述

在一个二维平面内，给定 $n$ 个整数点 $(x_i, y_i)$ ，此外你还可以自由添加 $k$ 个整数点。

你在自由添加 $k$ 个点后，还需要从 $n + k$ 个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 $1$ 而且横坐标、纵坐标值均单调不减，即 $x_{i+1} - x_i = 1, y_{i+1} = y_i$ 或 $y_{i+1} - y_i = 1, x_{i+1} = x_i$ 。请给出满足条件的序列的最大长度。

输入格式

第一行两个正整数 $n, k$ 分别表示给定的整点个数、可自由添加的整点个数。

接下来 $n$ 行，第 $i$ 行两个正整数 $x_i, y_i$ 表示给定的第 $i$ 个点的横纵坐标。

输出格式

输出一个整数表示满足要求的序列的最大长度。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

【样例 #3】

见附件中的 point/point3.in 与 point/point3.ans。

第三个样例满足 $k = 0$ 。

【样例 #4】

见附件中的 point/point4.in 与 point/point4.ans。

【数据范围】

保证对于所有数据满足： $1 \leq n \leq 500$ ， $0 \leq k \leq 100$ 。对于所有给定的整点，其横纵坐标 $1 \leq x_i, y_i \leq {10}^9$ ，且保证所有给定的点互不重合。对于自由添加的整点，其横纵坐标不受限制。

测试点编号	$n \leq$	$k \leq$	$x_i,y_i \leq$
$1 \sim 2$	$10$	$0$	$10$
$3 \sim 4$	$10$	$100$	$100$
$5 \sim 7$	$500$	$0$	$100$
$8 \sim 10$	$500$	$0$	${10}^9$
$11 \sim 15$	$500$	$100$	$100$
$16 \sim 20$	$500$	$100$	${10}^9$

解析

题目概述

在一个二维平面内，给定 $n$ 个整数点 ((x_i, y_i))，此外还可以自由添加 $k$ 个整数点。添加这 $k$ 个点后，需要从 $n+k$ 个点中选出若干个点，组成一个序列，要求满足以下条件：

序列中任意相邻两点间的欧几里得距离恰好为 1；
序列中的点，横坐标 $x$ $x$ 和纵坐标 $y$ $y$ 必须单调不减，即：
- $x_{i+1} - x_i = 1$ 且 $y_{i+1} = y_i$ ，或
- $y_{i+1} - y_i = 1$ 且 $x_{i+1} = x_i$ 。

要求输出满足上述条件的序列的最大长度。

约束条件

$n \leq 500$
$k \leq 100$
$x_i, y_i \leq 10^9$

思路概述

这个问题看起来像是二维平面的最长不下降子序列问题，因此我们可以考虑使用动态规划（DP）来解决。由于 $n$ 和 $k$ 的范围较小，我们可以使用时间复杂度为 $O(n^2k)$ 的三次方算法来解决。

首先，对输入的点按 $x$ 为第一关键字、 $y$ 为第二关键字进行排序，这样便于我们进行状态的转移。

动态规划状态定义

设状态 $f[i][j]$ 表示枚举到第 $i$ 个点，还剩余 $j$ 个自由点可添加，此时满足题意的序列的最大长度。

状态转移方程

根据题意，我们可以得到以下状态转移方程：

f[i][j] = \max(f[k][j+d] + d + 1)

其中 $k \in [1, i-1]$ ，并且 $d = |x_i - x_k| + |y_i - y_k| - 1$ ，表示从点 $k$ 到点 $i$ 之间需要添加多少个自由点才能使得距离符合条件。如果 $j + d > k$ ，则不能进行状态转移。

#include<bits/stdc++.h>
using namespace std;

const int N=510,K=110;

int n, k;
struct node{
    int x, y;
    bool operator< (const node &w) const {
        if(x == w.x) return y < w.y;
        return x < w.x;
        // 运算符重载，以x为第一关键字，以y为第二关键词从小到大排序
    }
}a[N];
int f[N][K];

int main() {
    // 输入 n 和 k
    scanf("%d%d", &n, &k);
    
    // 输入 n 个整数点的坐标
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &a[i].x, &a[i].y);
    
    // 对点进行排序
    sort(a + 1, a + 1 + n);
    
    // 动态规划过程
    for(int i = 1; i <= n; i++) {
        f[i][k] = 1; // 初始化第 i 个点，剩余 k 个自由点的情况
        for(int j = 0; j <= k; j++) {
            for(int t = 1; t < i; t++) {
                // 序列必须符合题意，横坐标和纵坐标均单调不减
                if(a[t].x > a[i].x || a[t].y > a[i].y) continue;
                
                // 计算从点 t 到点 i 之间需要加的自由点数
                int dx = abs(a[i].x - a[t].x);
                int dy = abs(a[i].y - a[t].y);
                int d = dx + dy - 1;
                
                // 如果需要加的自由点超过 k 个，跳过
                if(j + d > k) continue;
                
                // 状态转移
                f[i][j] = max(f[i][j], f[t][j + d] + d + 1);
            }
        }
    }
    
    // 最终答案
    int ans = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= k; j++)
            ans = max(ans, j + f[i][j]);  // 考虑剩余自由点的情况
    
    // 输出答案
    cout << ans;
    
    return 0;
}

代码解析

输入处理：首先输入 $n$ 和 $k$ ，接着读取每个点的坐标。
排序：对所有点按 $x$ 和 $y$ 进行排序，确保动态规划过程中的序列是合法的。
动态规划：使用三层嵌套循环，逐步转移状态。最内层循环计算从一个点到另一个点需要添加的自由点数，并更新状态。
输出答案：通过遍历所有可能的状态，找到能够构成的最大序列长度并输出。

小结

这个问题本质上是一个二维的最长子序列问题。通过引入动态规划来解决状态转移，结合适当的自由点添加条件，最终可以在 $O(n^2 k)$ 的时间复杂度内解决问题。