自动搬运

查看原文

来自洛谷，原作者为

	Yxa_Sheep 打表过样例，暴力出奇迹，搜索真牛逼，骗分进省一||深搜 MLE，广搜 TLE，打表 RE，退火又 CE||删掉 display 看主页||被封取关（解封后私信）||六年级蒟蒻 ，代词请用“他”||当前状态：<离线>

搬运于2025-08-24 21:17:33，当前版本为作者最后更新于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;
}

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

题目传送门