哈尔滨网站制作,网站不接入备案,网站开发营业执照申请,装修公司网页设计传送门 显然的 $dp$ 设 $f[i]$ 表示点击第 $i$ 个音符时的最大价值#xff0c;$t[i]$ 表示音符 $i$ 的准备时间 那么可以枚举 $1$ 到 $i-t[i]$ 的所有音符#xff0c;如果 $j$ #xff0c;如果 $jt[j]$ 小于等于 $i$ #xff0c;那么 $f[i]max(f[i],f[j]t[i]*val[i])$ 考虑…传送门 显然的 $dp$ 设 $f[i]$ 表示点击第 $i$ 个音符时的最大价值$t[i]$ 表示音符 $i$ 的准备时间 那么可以枚举 $1$ 到 $i-t[i]$ 的所有音符如果 $j$ 如果 $jt[j]$ 小于等于 $i$ 那么 $f[i]max(f[i],f[j]t[i]*val[i])$ 考虑优化转移 显然如果 $i$ 在时间 $k$ 时可以转移那么后面所有的时间也都能转移 考虑用树状数组维护前缀最大值用 $vector$ 维护时间 $k$ 时恰好可以转移的 $f$ 那么每次到一个位置就把可以转移的 $f$ 插到树状数组然后查询最大值转移 复杂度 $O(nlog_n)$注意 $long\ long$ #includeiostream
#includecstdio
#includealgorithm
#includecmath
#includecstring
#includevector
using namespace std;
typedef long long ll;
inline int read()
{int x0,f1; char chgetchar();while(ch0||ch9) { if(ch-) f-1; chgetchar(); }while(ch0ch9) { x(x1)(x3)(ch^48); chgetchar(); }return x*f;
}
const int N1e67;
int n,t[N],val[N];
ll T[N],f[N],ans;
inline void ins(int x,ll y) { while(xn) T[x]max(T[x],y),x(x-x); }
inline ll query(int x) { ll res0; while(x) resmax(res,T[x]),x-(x-x); return res; }
vector int v[N];
int main()
{freopen(fc.in,r,stdin);freopen(fc.out,w,stdout);nread();for(int i1;in;i) t[i]read();for(int i1;in;i) val[i]read();for(int i1;in;i){int lenv[i].size();for(int j0;jlen;j) ins(v[i][j], f[v[i][j]] );f[i]1ll*val[i]*t[i] (it[i] ? query(i-t[i]) : 0);if(it[i]n) v[it[i]].push_back(i);ansmax(ans,f[i]);}printf(%lld,ans);return 0;
} 转载于:https://www.cnblogs.com/LLTYYC/p/10490457.html
