导论
1.第一想法是贪心,但是很显然,贪心不行,如果a[i]很小,b[i]很大,b[i]就永远不会用到
2.所以要有动态规划的思想,即把每种可能的情况都保留下来,以后可能用到
一些事实
不管我怎么选择完成任务的顺序,我至少会把前i种任务完成至少一遍,即a[i]
在假设我最多只完成到前i种任务,那么后(n-i)个任务我一定选择完成前i种任务中b[i]最大的。
思路
遍历i:1-n,找出(a[1]+..+a[i])+(n-i)*(b[max])的最大值
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[200005]={0};
ll b[200005]={0};
ll psum[200005]={0};
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
psum[i]=psum[i-1]+a[i];
}
ll ans=0;
ll maxs=0;
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)
{
if(i>k)break;
maxs=max(b[i],maxs);
ans=max(ans,psum[i]+(k-i)*maxs);
}
cout<<ans<<endl;
}
return 0;
}