codeforces 855 B. Marvolo Gaunt’s Ring (前缀最大,dp)

题目链接

题意:给出n,p,q,r,以及n(1E5)个数,所有数的范围都是[-1E9,1E9],现在问pa[i]+qa[j]+r*a[k]的最大值,满足1<=i<=j<=k<=n

思路:傻逼dp…

我。。好菜啊。。。万年dp苦手。

直接转载官方题解了。。。思路的重点是维护了一个最大前缀值。

dp[i][0] stores maximum of value p·ax for x between 1 and i. Similarly dp[i][1] stores the maximum value of p·ax + q·ay such that x ≤ y ≤ i and dp[i][2] stores maximum value of p·ax + q·ay + r·az for x ≤ y ≤ z ≤ i.

To calculate the dp:

dp[i][0] = max(dp[i - 1][0], p·ai)

dp[i][1] = max(dp[i - 1][1], dp[i][0] + q·ai)

dp[i][2] = max(dp[i - 1][2], dp[i][1] + r·ai)

The answer will be stored in dp[n][2]

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz