双鸭山网站开发,用心做电影的网站,大连网站建设哪个公司好,一个人在线观看免费中文题链#xff1a; http://www.lydsy.com/JudgeOnline/problem.php?id1855 题解#xff1a; DP,单调队列优化。#xff08;好久没做 DP题#xff0c;居然还意外地想出来了#xff09; 定义 dp[i][k] 表示前 i天#xff0c;手上还有 k股的最大收益。#xff08;注意这个定… 题链 http://www.lydsy.com/JudgeOnline/problem.php?id1855 题解 DP,单调队列优化。好久没做 DP题居然还意外地想出来了 定义 dp[i][k] 表示前 i天手上还有 k股的最大收益。注意这个定义是个前缀的形式假设枚举到了第 i天令 ji-W-1。那么dp[i][]就由dp[j][]转移而来。说了是前缀形式的啦就不要去枚举 j-1j-2...了转移还是比较显然的枚举第 i 天结束手上还剩的股数 k 枚举今日购买 d张cmax(dp[i][k],dp[j][k-d]-d*AP) 枚举今日卖出 d张cmax(dp[i][k],dp[j][kd]d*BP) 然后再来一个前缀的转移cmax(dp[i][k],dp[i-1][k]); 这个复杂度是 T*MAXP*MAXP的只能过 50分。 考虑优化以购买转移为例显然转移的区间为连续的一段即若对于 dp[i][k]来说转移来源是 dp[j][k-1]~dp[j][k-AS]。 且不难发现如果 k-1xyk-AS,且 dp[j][x] dp[j][y]-val (val(x-y)*AP)那么如论如何dp[j][y]都不可能贡献答案。所以就用单调队列维护每次转移的最值就好啦。一个小技巧在从 计算 dp[i][k] 到 计算 dp[i][k1] 时显然单调队列里的旧元素的贡献相比刚刚加进队列的 newvaldp[j][k]来说都会减一个 AP 但不好整体修改难道你想用数据结构维护 所以就令新加进队列的值 newvaldp[j][k]k*AP保持好队列里的元素的相对大小关系就好了(即dp[j][k-1]始终比dp[j][k]多减了一个AP)。 卖出的转移就类似了。 最终复杂度可以做到 T*MAXP 代码 #includecstdio
#includecstring
#includeiostream
#define MAXN 2005
#define ll long long
#define filein(x) freopen(#x.in,r,stdin);
#define fileout(x) freopen(#x.out,w,stdout);
using namespace std;
ll dp[MAXN][MAXN],qv[MAXN],ANS,newval;
int T,MAXP,W,AP,BP,AS,BS,qk[MAXN];
void cmax(ll a,ll b){if(ab) ab;
}
int main()
{filein(trade); fileout(trade);memset(dp,0xcc,sizeof(dp)); dp[0][0]0;scanf(%d%d%d,T,MAXP,W);for(int i1,j,l,r;iT;i){ //2000scanf(%d%d%d%d,AP,BP,AS,BS);jmax(i-W-1,0);for(int k0;kMAXP;k)//50-2000 //前缀形式今日不做任何操作 cmax(dp[i][k],dp[i-1][k]);l1;r1; qk[l]0; qv[l]dp[j][0];for(int k1;kMAXP;k){//50-2000//购置 //for(int d1;dASk-d0;d) cmax(dp[i][k],dp[j][k-d]-1ll*d*AP);while(lrk-qk[l]AS) l;cmax(dp[i][k],dp[j][qk[l]]-1ll*(k-qk[l])*AP);newvaldp[j][k]1ll*k*AP;while(lrqv[r]newval) r--; r; qk[r]k; qv[r]newval; }l1;r1; qk[l]MAXP; qv[l]dp[j][MAXP];for(int kMAXP-1;k0;k--){//50-2000//出售 //for(int d1;dBSkdMAXP;d) cmax(dp[i][k],dp[j][kd]1ll*d*BP);while(lrqk[l]-kBS) l;cmax(dp[i][k],dp[j][qk[l]]1ll*(qk[l]-k)*BP);newvaldp[j][k]-1ll*(MAXP-k)*BP;while(lrqv[r]newval) r--; r; qk[r]k; qv[r]newval; }} //for(int k0;kMAXP;k) cmax(ANS,dp[T][k]);coutdp[T][0];return 0;
}转载于:https://www.cnblogs.com/zj75211/p/8005145.html
