CF573E Bear and Bowling 题解

一道比较玄学的 dp。

题意简述

给定一个长度为 $n$ 的序列 $a$。

要求序列 $a$ 的子序列 $b$,使 $b$ 满足 $\sum\limits_{i=1}^{m} i \cdot b_i$ 值最大。（$b$ 可以为空）

解题思路

非常简单就能想到 $Θ(n^2)$ 的代码。

状态转移方程:$dp_i=\max(dp_i, dp_{i-1} + i \cdot a_i)$。

这里的 $dp$ 用来记录到 $i$ 为止的子序列最大值，所以我们从大到小搜索。

显然，最后再从头到尾扫一遍记录最大值存在 $ans$ 中即可。

当然，$ans$ 可能小于 $0$，所以我们要对 $dp$ 数组初始化 $-\inf$。

代码实现

注意，这里要开 C++ 20！

#include<iostream>
#define inf LONG_LONG_MAX
using namespace std;
long long n,tmp,ans,dp[100010];
int main() {
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) dp[i]=-inf;
    for(int i=1;i<=n;i++) {
    	scanf("%lld",&tmp);
    	for(int j=i;j>0;j--) dp[j]=max(dp[j],dp[j-1]+j*tmp);
    }
    for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
    printf("%lld",ans);
    return 0;
}
//code by TheCedar