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

· · 题解

题目传送门

思路

最优化问题，考虑动态规划。

状态定义 ：dp_{i,j} 表示复习到第 i 天选 j 门功课的最大收益。

由于收益的计算方式与子段和有关，所以我们在设计状态转移方程式要考虑继承 / 不继承 上次的子段和。

先考虑继承，即上一天（第 i-1 天）也选 j 门功课，这次复习产生的收益是 a_i×b_j（用乘法分配律拆开之后的柿子），那么产生的总收益为 dp_{i-1,j}+a_i×b_j。

考虑不继承，即上一天选 j-1 门功课，加上这次复习的收益，产生的总收益为 dp_{i-1,j-1}+a_i×b_j。

综上，可得状态转移方程为 dp_{i,j}=max\{dp_{i-1,j},dp_{i-1,j-1}\}+a_i×b_j。

时间复杂度 O(Tnm)。

还有几个小点需要注意：

  1. 总收益可能为负数，所以 dp 数组初始化成负无穷。
  2. 十年 OI 一场空，不开long long见祖宗。

Code

#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef long long ll;
const int N = 2e3 + 10;
ll a[N], b[N];
ll dp[N][N];
int n, m;
il void init()
{
    cin >> n >> m;
    for(int i = 1;i <= n;++i)
        scanf("%lld", &a[i]);
    for(int i = 1;i <= m;++i)
        scanf("%lld", &b[i]);
}
il void solve()
{
    memset(dp, -0x3f, sizeof(dp));
    dp[0][0] = 0;
    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= m;++j)
            dp[i][j] = max(dp[i - 1][j] + a[i] * b[j], dp[i - 1][j - 1] + a[i] * b[j]);
    cout << dp[n][m] << "\n";
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        init();
        solve();
    }
    return 0;
}