游戏

游戏 都快CSP复赛了，我发现我贪心还是不好。。。。 上来先来个dp，发现写了个假结论。。。 —————————————————————————————————————— 其实这题应该考虑贪心，我们 $枚举3个数为例子，i，j，k，发现直接去k的价值和间接去k的价值分别为$ $(k-i)\ast a[k]$ $(j-i)\ast a[j]+(k-j)\ast a[k]$ $发现当a[k]>a[j]的时候，肯定直接去k更优$ 接下来只用找出后面的最大值就行了 $本人做法O(nlo{g}^{2}n)$：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=100010; int n,a[N],lg[N]; int st[N][18]; int maxn(int l,int r){ if(r<l) return 0; int len=(r-l+1); int ll=lg[len]; return max(st[l][ll],st[r-(1<<ll)+1][ll]); } int find(int l,int r){ while(l<r){ int mid=(l+r)>>1; if(maxn(l,mid)>maxn(mid+1,r)){ r=mid; } else l=mid+1; } return l; } int summ=0,lastt=1; int main(){ scanf("%d",&n); lg[0]=1; for(int i=2;i<=n;i++){ if(lastt*2==i){ lastt=i; lg[i]=++summ; continue; } lg[i]=summ; } for(int i=1;i<=n;i++){ scanf("%d",&a[i]); st[i][0]=a[i]; } int up=lg[n]; for(int i=1;i<=up;i++){ for(int l=1;l+(1<<i)-1<=n;l++){ int r=(l+(1<<i)-1); st[l][i]=max(st[l][i-1],st[l+(1<<(i-1))][i-1]); } } ll ans=0; int l=0;a[0]=0; while(l<n){ int nxt=find(l+1,n); ans+=1ll*(nxt-l)*a[nxt]; l=nxt; } printf("%lld",ans); }

其它O（n）做法 1.建递增队列，使队列中元素单调递增

#include<bits/stdc++.h> using namespace std; const int N=100010; int n,a[N]; int sstack[N][2]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } int cnt=0; for(int i=1;i<=n;i++){ sstack[++cnt][0]=a[i],sstack[cnt][1]=i; while(sstack[cnt-1][0]<sstack[cnt][0]&&cnt>1){ sstack[cnt-1][0]=sstack[cnt][0]; sstack[cnt-1][1]=sstack[cnt][1]; cnt--; } } long long ans=0; for(int i=1;i<=cnt;i++){ ans+=1ll*(sstack[i][1]-sstack[i-1][1])*sstack[i][0]; } printf("%lld",ans); }

2.逆序处理最大值，因为本题是求后面的最大值，所以直接求即可

P.S 遇到貌似dp的题一定要先想贪心