本文主要是介绍CF855B Marvolo Gaunt's Ring，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

洛谷题面

题目大意

给定 \(n,p,q,r\)，并且给出 \(n\) 个数。

在这些数中找 \(i,j,k(1\le i\le j\le k\le n)\)，求出 \(\max\{p\times a_i+q\times a_j+r\times a_k\}\)。

题目分析

一道小清新 \(\rm DP\) 题。

设 \(dp[idx][0]\) 表示前 \(idx\) 个数的 \(\max\{p\times a_i\}(1\le i\le idx)\)。

\(dp[idx][1]\) 表示前 \(idx\) 个数的 \(\max\{p\times a_i+q\times a_j\}(1\le i\le j\le idx)\)。

\(dp[idx][2]\) 表示前 \(idx\) 个数的 \(\max\{p\times a_i+q\times a_j+r\times a_k\}(1\le i\le j\le k\le idx)\)。

于是顺推即可：

\(dp[idx][0]=\max\{dp[idx-1][0],p\times a_i\}\)

\(dp[idx][1]=\max\{dp[idx-1][1],dp[idx][0]+q\times a_i\}\)

\(dp[idx][2]=\max\{dp[idx-1][2],dp[idx][1]+r\times a_i\}\)

初始化：

• \(dp[idx][0]=p\times a_1\)

• \(dp[idx][1]=p\times a_1+q\times a_1\)

• \(dp[idx][2]=p\times a_1+q\times a_1+r\times a_1\)

最后答案就是 \(dp[n][2]\)。

时间复杂度为 \(\operatorname{O}(N)\)。

注意开 \(\rm long~long\)。

代码

//2021/11/14

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>

#include <climits>//need "INT_MAX","INT_MIN"

#define int long long

#define enter() putchar(10)

#define debug(c,que) cerr<<#c<<" = "<<c<<que

#define cek(c) puts(c)

#define blow(arr,st,ed,w) for(register int i=(st);i<=(ed);i++)cout<<arr[i]<<w;

#define speed_up() std::ios::sync_with_stdio(false)

namespace Newstd
{
	inline int read()
	{
		char c;
		bool flag=false;
		while((c=getchar())<'0' || c>'9')
		{
		    if(c=='-') flag=true;
		}
		int res=c-'0';
		while((c=getchar())>='0' && c<='9')
		{
		    res=(res<<3)+(res<<1)+c-'0';
		}
		return flag?-res:res;
	}
	inline void print(int x)
	{
		if(x<0)
		{
			putchar('-');x=-x;
		}
		if(x>9)
		{
			print(x/10);
		}
		putchar(x%10+'0');
	}
}

using namespace Newstd;

using namespace std;

const int ma=100005;

int a[ma];

int dp[ma][3];
/*
dp[i][0]:前 i 个数中取 p*a_i 最大值
dp[i][1]:前 i 个数中取 p*a_i+q*a_j 最大值
dp[i][2]:前 i 个数中取 p*a_i+q*a_j+r*a_k 最大值 
*/

int n,p,q,r;

#undef int

int main(void)
{
	#define int long long
	
	n=read(),p=read(),q=read(),r=read();
	
	for(register int i=1;i<=n;i++)
	{
		a[i]=read();
	}
	
	dp[1][0]=p*a[1];
	
	for(register int i=2;i<=n;i++)
	{
		dp[i][0]=max(dp[i-1][0],p*a[i]);
	}
	
	dp[1][1]=p*a[1]+q*a[1];
	
	for(register int i=2;i<=n;i++)
	{
		dp[i][1]=max(dp[i-1][1],dp[i][0]+q*a[i]);
	}
	
	dp[1][2]=p*a[1]+q*a[1]+r*a[1];
	
	for(register int i=2;i<=n;i++)
	{
		dp[i][2]=max(dp[i-1][2],dp[i][1]+r*a[i]);
	}
	
	printf("%lld\n",dp[n][2]);
	
	return 0;
}

这篇关于CF855B Marvolo Gaunt's Ring的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！