CF573E 题解

徐天乾 · 2022-02-11 18:56:13 · 题解

思路

根据题意，我们可以列出动态转移方程 dp_{i}=\max(dp_{i-1}+i \times a_{j})，dp_{x} 表示现在子序列有 x 个元素。很明显 O(n^2) 达到 10^{10}，正常是通不过的，但是它过了...

程序

#include<bits/stdc++.h>
using namespace std;
long long i,j,n,x,Max,dp[100010];
signed main(){
    scanf("%lld",&n);
    for (i=1;i<=n;i++) dp[i]=-1e18;
    for (i=1;i<=n;i++){
        scanf("%lld",&x);
        for (j=i;j>0;j--) dp[j]=max(dp[j],dp[j-1]+j*x); 
        }
    for (i=1;i<=n;i++) Max=max(Max,dp[i]);
    printf("%lld\n",Max);
    return 0;
}

后记

使用语言 C++20，最慢的点跑了 3.59s，对于 6.00s 的时间限制绰绰有余。 至于为什么这么快，小蒟蒻也不知道（本来想写暴力再用火车头等等优化尝试艹过去但是一遍就过了那档事）。