给了三个数: p,q,r(−1e9<=p,q,r<=1e9)p,q,r(−1e9<=p,q,r<=1e9)
然后给了n个数a1,a2...an(−1e9<=ai<=1e9)a1,a2...an(−1e9<=ai<=1e9)
求找出三个数ai,aj,ak(1<=i<=j<=k<=n)ai,aj,ak(1<=i<=j<=k<=n)使得p×ai+q×aj+r×akp×ai+q×aj+r×ak最大。
直接dp了
f[ i ][ 3] = f[i-1][3] + f[i-1][2]+a3*
f[i][2] = f[i-1][2]+ f[i-1][1]+a2*
f[i][1] =f[i-1][1]+ a1
#include <iostream> #include<queue> #include <cstring> #define IOS std::ios::sync_with_stdio(0) using namespace std; const int N =1e5+3; #define int long long int f[N][4],a[N],n,a1,a2,a3; void solve(){ int i,j; cin>>n>>a1>>a2>>a3; for(i=1;i<=n;i++)cin>>a[i]; f[1][1]=a[1]*a1; for(i=2;i<=n;i++){ f[i][1]=max(f[i-1][1],a1*a[i]); } f[1][2]=f[1][1]+a[1]*a2; for(i=2;i<=n;i++){ f[i][2]=max(f[i-1][2],f[i][1]+a2*a[i]); } f[1][3]=f[1][2]+a[1]*a3; for(i=2;i<=n;i++){ f[i][3]=max(f[i-1][3],f[i][2]+a3*a[i]); } cout<<f[n][3]<<endl; } signed main(){ IOS; solve(); }
标签:CF855B,int,Marvolo,long,a1,a3,a2,Ring,include From: https://www.cnblogs.com/towboa/p/17150887.html