Codeforces 855B 简单DP-白红宇

Codeforces 855B 简单DP

阅读量：5326 次

发布时间：2019-06-14

本文共 1289 字，大约阅读时间需要 4 分钟。

传送门：

emmmmmm……n比较打，1e15直接暴力的话会T，还有要注意的一点就是选取的ai,aj,ak,下标满足i<=j<=k，orz做的时候没注意WA了好多次orz

这里要用到的是简单的DP，循环扫2遍分别从头到尾，从尾到头记录至今为止的最大最小值，（因为要求pai+qaj+rak的最大值，所以只需要p,q,r>0时*最大值，<0时*最小值就好了，问题就在于如何处理下标不交叉的问题，dp的思想就是用来处理下标和最值之间的问题）从头到尾扫一遍记录的是ai在取aj时的值，从尾到头记录的是ak在取aj时的值，然后只需要再扫一遍记录到i处pai+qaj+rak的最大值就可以了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          using namespace std;typedef long long ll;ll a[100005];int n, p[3];ll maxx1[100005], minn1[100005];ll maxx2[100005], minn2[100005];int main(){ cin >> n; cin >> p[0] >> p[1] >> p[2]; for (int i = 1; i <= n; i++) cin >> a[i]; minn1[0]=1e18; maxx1[0] = -1e18; minn2[n + 1] = 1e18; maxx2[n + 1] = -1e18; for (int i = 1; i <= n; i++) { maxx1[i] = max(maxx1[i - 1], a[i]); minn1[i] = min(minn1[i - 1], a[i]); } for (int i = n; i >= 1; i--) { maxx2[i] = max(maxx2[i + 1], a[i]); minn2[i] = min(minn2[i + 1], a[i]); } ll ans = -4e18; for (int i = 1; i <= n; i++) { ll tmp = 0; if (p[0] >= 0) tmp += p[0] * maxx1[i]; else tmp += p[0] * minn1[i]; if (p[2] >= 0) tmp += p[2] * maxx2[i]; else tmp += p[2] * minn2[i]; ans = max(ans, tmp + p[1] * a[i]); } cout << ans << endl; return 0;}

转载于:https://www.cnblogs.com/Egoist-/p/7596911.html

你可能感兴趣的文章