Oiclass P1479 题解

这道题又又又又又是动规（我最近在学）

传统的五步：

1. 划分阶段

这里划分的阶段是在某个格子上时的最优解

2. 确定状态和状态变量

这里的状态数组 \(f\) 来进行存储，用数组 \(a\) 储存输入的数组。状态从他前面的格子获得，这些格子可能是： \[ a_{S},\ a_{S+1},\ a_{S+2}...a_{T-2},\ a_{T-1},\ a_{T} \]

3. 确定决策并写出状态转移方程

又到了烧脑的一步，不过对于这道题，我个人觉得还好。\(\huge 进入正题\)

我们从题目可以得知，我们希望 \(f_n\) 的值尽量大，越大越好，所以我们要尽量从大的格子转移状态，可以得到，我们可以转移状态的格子分别是 \(f_{S}\to f_T\) 的所有格子，也就是说我们要找出在 \(f_S \to f_T\) 之间最大的一个格子（包含 \(f_S\) 和 \(f_T\)）然后我们再拿上当前位置的格子，同时我们还需要考虑是直接拿上格子原来的金块多，还是拿上前面的金块多。OK，思路清晰了，开始写方程： \[ \begin{array}{lr} 对于第\ i\ 个状态:f_i\\ f_i = \max\left (\left(\max_{j=S,\ j++}^{0\ <\ j\ <\ T} f_j\right)+a_i,\ f_i\right) \end{array} \]

4. 确定初始值

初始值在这道题很简单，就是第一项，毕竟在第一项的时候除了这一项，你无法获得其他项的金块，故初始值如下： \[ f_1=a_1 \]

5. 实现

有了前面的分析，实现的思路也就很清晰了。

• 首先输入数据
• 枚举数组的每一个数，并使用状态转移方程计算他的值
• 输出 \(f_n\)

然后依分析模拟就可以得到代码。

注意以下几点：

• 在计算 \(f_{S} \to f_T\) 的所有格子的最大值时，要注意是否存在负数下标，如果存在，不应该将此计入计算范围，否则样例都过不了

#include <iostream>

using namespace std;

int n, s, t, a[1009], f[1009];

int main() {
    cin >> n >> s >> t;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    f[1] = a[1];
    for (int i = 2; i <= n; i++) {
        for (int j = s; j <= t; j++) {
            if (i - j > 0) {
                f[i] = max(f[i], f[i - j] + a[i]);
            }
        }
    }
    cout << f[n];
}