傳送門

顯然的 $dp$

設 $f[i]$ 表示點擊第 $i$ 個音符時的最大價值，$t[i]$ 表示音符 $i$ 的準備時間

那么可以枚舉 $1$ 到 $i-t[i]$ 的所有音符，如果? $j$ ，如果 $j+t[j]$ 小于等于 $i$ ，那么 $f[i]=max(f[i],f[j]+t[i]*val[i])$

考慮優化轉移

顯然如果 $i$ 在時間 $k$ 時可以轉移，那么后面所有的時間也都能轉移

考慮用樹狀數組維護前綴最大值，用 $vector$ 維護時間 $k$ 時恰好可以轉移的 $f$

那么每次到一個位置就把可以轉移的 $f$ 插到樹狀數組，然后查詢最大值轉移

復雜度 $O(nlog_n)$，注意 $long\ long$

#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> using namespace std; typedef long long ll; inline int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }return x*f; } const int N=1e6+7; int n,t[N],val[N]; ll T[N],f[N],ans; inline void ins(int x,ll y) { while(x<=n) T[x]=max(T[x],y),x+=(x&-x); } inline ll query(int x) { ll res=0; while(x) res=max(res,T[x]),x-=(x&-x); return res; } vector <int> v[N]; int main() {freopen("fc.in","r",stdin);freopen("fc.out","w",stdout);n=read();for(int i=1;i<=n;i++) t[i]=read();for(int i=1;i<=n;i++) val[i]=read();for(int i=1;i<=n;i++){int len=v[i].size();for(int j=0;j<len;j++) ins(v[i][j], f[v[i][j]] );f[i]=1ll*val[i]*t[i]+ (i>t[i] ? query(i-t[i]) : 0);if(i+t[i]<=n) v[i+t[i]].push_back(i);ans=max(ans,f[i]);}printf("%lld",ans);return 0; }

?

轉載于:https://www.cnblogs.com/LLTYYC/p/10490457.html

總結

以上是生活随笔為你收集整理的「2019冬令营提高组」全连的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。