专栏文章

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

AA7F3jK9pR0xf_
B4172题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipo1bb6
此快照首次捕获于
2025/12/03 15:08
3 个月前
此快照最后确认于
2025/12/03 15:08
3 个月前
查看原文

题目传送门

思路

最优化问题，考虑动态规划。
状态定义 ：dpi,jdp_{i,j} 表示复习到第 ii 天选 jj 门功课的最大收益。
由于收益的计算方式与子段和有关，所以我们在设计状态转移方程式要考虑继承 / 不继承 上次的子段和。
先考虑继承，即上一天（第 i−1i-1 天）也选 jj 门功课，这次复习产生的收益是 ai×bja_i×b_j（用乘法分配律拆开之后的柿子），那么产生的总收益为 dpi−1,j+ai×bjdp_{i-1,j}+a_i×b_j。
考虑不继承，即上一天选 j−1j-1 门功课，加上这次复习的收益，产生的总收益为 dpi−1,j−1+ai×bjdp_{i-1,j-1}+a_i×b_j。
综上，可得状态转移方程为 dpi,j=max{dpi−1,j,dpi−1,j−1}+ai×bjdp_{i,j}=max\{dp_{i-1,j},dp_{i-1,j-1}\}+a_i×b_j。
时间复杂度 O(Tnm)O(Tnm)。
还有几个小点需要注意：
  1. 总收益可能为负数，所以 dpdp 数组初始化成负无穷。
  2. 十年 OI 一场空，不开long long见祖宗。

CodeCode

CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...