「2019冬令營提高組」全連

傳送門

顯然的 $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;
}

?