WordPress网站转APP插件,网站域名是什么东西,医院网站模板 html,产品介绍网站设计怎么做题目描述
暑假共有 n 天#xff0c;第 i 天的精力指数为 a[i]#xff0c;你想要利用假期依次#xff08;按 1,2,...,m 顺序#xff09;复习 m 门功课#xff0c;第 i 门功课的重要程度为 b[i]#xff0c;且每门的复习时段必须连 续#xff0c;并且不能有某天不干事。
…题目描述
暑假共有 n 天第 i 天的精力指数为 a[i]你想要利用假期依次按 1,2,...,m 顺序复习 m 门功课第 i 门功课的重要程度为 b[i]且每门的复习时段必须连 续并且不能有某天不干事。
假设第 i 门功课的复习时段为第 l∼r 天那么第 i 门功课的收益为 b[i]×(a[l]a[l1]...a[r])你的总收益为 m 门功课收益的总和。
请你制订一个复习计划使得总收益最大。
形式化地给定序列 a[1∼n],b[1∼m]你需要把 1,2,...,n 这个序列分成首尾相 连且非空的 m 段假设每段的 a 之和为 s[1∼m]最大化 ∑i1mb[i]×s[i] 的值。
例如 a[−3,6,−1,−8,7,−6],b[−3,2]最优策略是第 1∼4 天复习第 1 门功课收益为 −3×(−36−1−8)18第 5∼6 天复习第 2 门功课收益为 2×(7−6)2总收益为 18220。
例如 a[6,3,5,10,5],b[−8,−5,−5]最优策略是分成 [1],[2,3,4],[5] 三段总收益为 −8×6−5×(3510)−5×5−163。
输入格式
第一行为 1 个整数 T代表有 T 组数据。
每组数据第一行 2 个整数 n,m第二行 n 个整数 a[1∼n]第三行 m 个整数 b[1∼m]。
输出格式
输出 T 行每行 1 个整数代表答案。
样例 #1
样例输入 #1
5
6 2
-3 6 -1 -8 7 -6
-3 2
5 4
-9 -6 -6 -7 -8
-5 7 -9 -3
7 7
7 2 3 0 -2 4 2
-9 -2 -5 0 -7 9 -1
5 3
10 4 6 7 4
-1 -9 2
5 3
6 3 5 10 5
-8 -5 -5
样例输出 #1
20
144
-34
-12
-163
提示
对于所有数据满足 1≤T≤201≤m≤n≤2000−10^3≤a[i],b[i]≤10^3 。
对于测试点 1∼7n≤10
对于测试点 8∼12n≤500
对于测试点 13∼16所有 a[i],b[i] 均为正整数
对于测试点 17∼20n≤2000
#include bits/stdc.h
using namespace std;int a[2010],b[2010];//-1e3~1e3 -1e3~1e3
int dp[2010];//-2e9~2e9
int main()
{int t;//1~2e1cint;while(t--){memset(dp,0x80,sizeof(dp));int n,m;//1~2e3cinnm;for(int i1;in;i)cina[i];for(int i1;im;i)cinb[i];dp[1]a[1]*b[1];for(int i2;in;i)for(int jm;j1;j--)dp[j]a[i]*b[j]max(dp[j-1],dp[j]);coutdp[m]endl;}return 0;
}
背景 这道题是我考BCSP-X的T3当时直接爆零……
主题思路 首先最重要的一点——你得意识到这是个DP。在这之后要思考几件事。 1.不出意外的话这是个二维dp毕竟是T3。 2.直觉告诉我们dp[i][j]里存的是到i为止的最大收益。那第一、二维代表什么可以找题目中的时间状态以及其他变量。有时间天那第一维就是天。很显然第二维最合适的的是科目因为它与时间没有什么关联而且是决定答案的关键因素之一。 3.dp[i][j]是由什么推导而来的即第1~i天如果选择第j门功课最大收益与什么有关联走到这一步时首先要加上今天本身的收益——a[i]*b[j]紧接着要加第1~i-1天的最大收益这时你有两个选择要选最大值。如果你仍延续了昨天的选择如继续学习语文那么要加上dp[i-1][j]时间变为昨天科目不变如果你换了一科如改为学习数学那么要加上dp[i-1][j-1]时间变为昨天科目变为上一个科目。注意题目中说“你想要利用假期依次按 1,2,...,m 顺序复习 m 门功课”那么你就只能是紧挨着你的上一个功课变来的。 接下来就没什么了由3.我们可以得到最最最重要的状态转移方程式dp[i][j]a[i]*b[j]max(dp[i-1][j-1],dp[i-1][j]);就……做完了。
细节重点 1.由于是多组数据肯定少不了memset。a、b数组会覆盖不用管但是dp要给赋值成极小值。这是因为在max(dp[j-1],dp[j])处可能会取到尚未赋值的dp区域如果赋值的部分是负数理论上应取这个负数但如果置成0就会取0所以最开始要赋值为极小值0x80808080让他“被迫”选这个复数。 2.写完之后你会发现这道题像极了01背包相应的你也可以做同样的空间压缩。由于每次只与上一行有推导关系可以将第一维删去。需要注意的是如果你想访问上一轮的数据在递推的第二层循环处你需要改成逆序。
