题解：B4172 [BCSP-X 2024 6 月小学高年级组] 学习计划

Yxa_Sheep · 2025-07-03 19:10:02 · 题解

题目传送门

题意

用 n 天复习 m 个科目，每门科目的复习时间连续。第 i 门科目从第 l 天复习到第 r 天的收益为 b_i\times (a_l+a_{l+1}+\dots+a_{r-1}+a_r)，求最大总收益。

思路

算法标签都挂着 DP，那我们当然得用了：

• 用 f_{i,j} 表示复习到第 i 天选择 j 门科目的最大收益。
• 首先考虑特殊情况，i=0 或者 j=0 时 f_{i,j}=0。
• 接着考虑普通情况，如果第 i-1 天选 j 门科目（f_{i-1,j} 嘛），那么 f_{i,j}=f_{i-1,j}+a_i\times b_j（a_i\times b_j 是从题目中那个 b_i\times (a_l+a_{l+1}+\dots+a_{r-1}+a_r) 中分解出来的，乘法分配律嘛），如果 i-1 天选 j-1 个科目，那么第 i 天就是第一个选第 j 个科目的，那么 f_{i,j}=f_{i-1,j-1}+a_i\times b_j。

  代码

#include <bits/stdc++.h>
using namespace std;
int t, n, m, a[2010], b[2010], f[2010][2010];
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for (int i = 1; i <= m; i++)
            scanf("%d", &b[i]);
        memset(f, -0x3f, sizeof(f)), f[0][0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                f[i][j] = max(f[i - 1][j], f[i - 1][j - 1]) + a[i] * b[j];
        printf("%d\n", f[n][m]);
    }
    return 0;
}

题解来之不易，且看且珍惜。给个赞再走吧。

题目传送门