cn域名做外贸网站,网络广告设计公司,海口网上注册公司流程,爱淘宝淘宝网首页全局最优解必然包含局部最优解#xff0c;因此每次转移只需考虑局部最优解#xff01;#xff01;#xff01; 主要内容 形如这样 的 \(\operatorname{DP}\) 转移方程#xff1a; \[dp[i]\max_{L_i\le j\le R_i}{\{dp[i]val(i,j)\}} \]满足#xff1a; \(\{L_i\}\) , \(\… 全局最优解必然包含局部最优解因此每次转移只需考虑局部最优解 主要内容 形如这样 的 \(\operatorname{DP}\) 转移方程 \[dp[i]\max_{L_i\le j\le R_i}{\{dp[i]val(i,j)\}} \]满足 \(\{L_i\}\) , \(\{R_i\}\) 递增( 前提条件 )。 \(R_i \le i\) ( 转移条件 )。 \(val(i,j)\) 值只与 \(j\) 相关 ( 根本优化转移前提 ) 。 维护一个滑动窗口每次求窗口中的最大值。对于两个点 \(x\) \(y\) 如果 \(x y\) 且 \(f(x) f(y)\) 那么 \(y\) 进入窗口后决策点一定不会是 \(x\) 。 用一个单调队列维护窗口里所有可能用到的决策点。 窗口右端点向右滑动时把一个新的点插入队尾。队尾点为 \(q[r]\) 新点为 \(x\) 如果 \(f(q[r]) \le f(x)\) 那么 \(q[r]\) 没用把 \(q[r]\) 弹掉。重复过程直到队尾点可能有用即 \(f(q[r]) f(x)\) 把 \(x\) 入队。 队列中的 \(f(i)\) 从队首到队尾递减。决策时首先弹掉队首超过范围的点。这时队首点就是决策点。\(f(i) \max {\{f(j) w_i\}} [i-R_i \le j \le i-L_i]\) 单调队列优化 也称为 滑动窗口 。 变式 \(-\) 单调队列优化多重背包 内容 设 \(dp[i][j]\) 表示前 \(i\) 个物品放入容量为 \(j\) 的背包的最大收益 。 \[dp[i][j]\max_{k0}^{k\le k[i]}{\{dp[i-1][j-k\times c[i]]k\times w[i]\}} \]考虑 \(dp\) 的转移 。 \[0\le p c[i],0\le j \le \left\lfloor \dfrac{V-p}{c[i]}\right\rfloor,0\le k \le k[i] \]\[dp[i][pj\times c]\max{\{dp[i-1][p(j-k)\times c]k\times w\}} \]\[dp[i][pj\times c]\max{\{dp[i-1][p(j-k)\times c]-(j-k)\times wj\times w\}} \]\[dp[i][pj\times c]\max{\{dp[i-1][p(j-k)\times c]-(j-k)\times w\}}j\times w \]这样就可以进行单调队列优化了 。 时间复杂度\(O(nV)\) 。 核心代码( P1776 宝物筛选 ) 代码中的 \(pos\) 就是上面的 \(j-k\) 。 int ql,qr;
struct QUE
{int num,val;
}que[Maxv];
void many_pack(int c,int w,int m)
{if(!c) { addm*w; return; }mmin(m,V/c);for(int pos0,s;posc;pos){ql1,qr0,s(V-pos)/c;for(int j0;js;j){while(qlqr que[qr].val(dp[posj*c]-j*w)) qr--;que[qr](QUE){j,dp[posj*c]-j*w};while(qlqr (j-que[ql].num)m) ql;dp[posj*c]max(dp[posj*c],que[ql].valj*w);}}
} 多重背包的其他解法二进制分组优化 时间复杂度 \(O(V\sum_{i1}^{n}\log_2{k_i})\) 见背包问题 。 注意 用结构体存储单调队列防止反复修改 \(dp\) 值。 并注意 \(j0\) 时的情况及时更新。 二维单调队列 对于每一列维护一个竖直方向上的一维单调队列。 在每一行统计答案的时候用一个新的一维单调队列维护每一列的最优答案。 最终答案在新的一维单调队列上。 例题P2219 [HAOI2007]修筑绿化带 例题 P1725 琪露诺 $\texttt{solution}$ 状态设 \(dp[i]\) 表示走到 \(i\) 的最大收益。 \(L\) 与 \(R\) 都是上文中的转移范围。 核心代码 nrd(),tmplrd(),tmprrd();
for(int i0;in;i) a[i]rd();
for(int i1;in;i) L[i]i-tmpr,R[i]i-tmpl;
memset(dp,-inf,sizeof(dp));
dp[0]a[0];
for(int i1;in;i) // 必须从 l 开始
{if(R[i]0) continue;while(lr q[l]L[i]) l;while(lr dp[q[r]]dp[R[i]]) r--;q[r]R[i]; // 因为 i-L 小于 i 所以应该确保最有决策再进行转移 dp[i]dp[q[l]]a[i];
}
int ans-inf;
for(int iL[n]1;in;i) ansmax(ans,dp[i]);
printf(%d\n,ans); P3572 [POI2014]PTA-Little Bird $\texttt{solution}$ 状态\(dp[i]\) 表示到 \(i\) 为止的最小代价。 核心代码 bool Better(int x,int y)
{if((dp[x]dp[y]) || (dp[x]dp[y] h[x]h[y])) return true;return false;
}
for(int i1;in;i) L[i]i-k,R[i]i-1;
q[1]lr1;
for(int i2;in;i)
{if(R[i]0) continue;while(lr q[l]L[i]) l;while(lr Better(R[i],q[r])) r--;q[r]R[i];dp[i]dp[q[l]](h[q[l]]h[i]);
}
printf(%d\n,dp[n]); P3957 跳房子 $\texttt{solution}$ 注意点 存储要开 \(\texttt{long}~\texttt{long}\) 。 注意转移的左右端点判断问题。 代码 bool check(int g)
{memset(dp,-inf,sizeof(dp)),dp[0]0;memset(L,inf,sizeof(L)),memset(R,-1,sizeof(R));int tlmax(1,d-g),trdg;ll MAX-inf;for(int i0,tmpr0;in;i) // 判断左端点 while(tmprn pos[i]trpos[tmpr]) L[tmpr]i;for(int in,tmpln;i0;i--) // 判断右端点 {while(pos[i]trpos[tmpl]) tmpl--; // 可能没有右端点 while(tmpl0 pos[i]tlpos[tmpl] pos[i]trpos[tmpl]) R[tmpl--]i;}for(int i1,l1,r0;in;i){if(L[i]R[i]) continue;while(lr q[l]L[i]) l;for(int jmax(R[i-1]1,L[i]);jR[i];j) // 右端点不一定是连续的而且可能是 -1 {while(lr dp[q[r]]dp[j]) r--;q[r]j;}if(lr) dp[i]dp[q[l]]val[i];}for(int i0;in;i) MAXmaxll(MAX,dp[i]);return (MAXk);
}int l1,rpos[n];
while(lr)
{int mid(lr)/2;if(check(mid)) ansmid,rmid-1;else lmid1;
}
printf(%d\n,ans); P1099 树网的核 \(\\) P2491 [SDOI2011]消防(加强版 树网的核) $\texttt{solution}$ 求直径( 这应该都会 ) 。 在直径上单调队列求出不大于 \(s\) 的一个区间使区间两端到直径两端的最大值最小 ( 即那一段区间的 \(\operatorname{GCC}\) ) 对每一个直径上的点求到有这个点伸出去的最远距离与答案取 \(\max\) 。 \(Finish\) 代码 #includebits/stdc.h
using namespace std;
#define infll 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define Maxn 500005
typedef long long ll;
inline int rd()
{int x0;char ch,t0;while(!isdigit(ch getchar())) t|ch-;while(isdigit(ch)) xx*10(ch^48),chgetchar();return xt?-x:x;
}
int n,s,tot,root1,root2,cnt,tmp,ansinf;
int d[Maxn],fa[Maxn],que[Maxn],mx[Maxn],addmx[Maxn];
int hea[Maxn],nex[Maxn*2],ver[Maxn*2],edg[Maxn*2];
bool isdia[Maxn];
void add(int x,int y,int d)
{ver[tot]y,edg[tot]d,nex[tot]hea[x],hea[x]tot;
}
void dfs(int x)
{for(int ihea[x];i;inex[i]){if(ver[i]fa[x]) continue;fa[ver[i]]x;d[ver[i]]d[x]edg[i];dfs(ver[i]);}
}
void dfs2(int x,int F,int dis)
{ansmax(ans,dis);for(int ihea[x];i;inex[i]){if(ver[i]F || isdia[ver[i]]) continue;dfs2(ver[i],x,disedg[i]);}
}
int main()
{//freopen(.in,r,stdin);//freopen(.out,w,stdout);nrd(),srd();int u,v,eg;for(int i1;in;i){urd(),vrd(),egrd();add(u,v,eg),add(v,u,eg);}dfs(1);for(int i1;in;i) if(d[i]d[root1]) root1i;fa[root1]0,d[root1]0;dfs(root1);for(int i1;in;i) if(d[i]d[root2]) root2i;for(tmproot2;tmp!root1;tmpfa[tmp]) mx[cnt]d[tmp],isdia[tmp]true;mx[cnt]0,isdia[root1]true;for(int i1,l1,r0;icnt;i){while(lr mx[que[l]]mx[i]s) l;que[r]i;ansmin(ans,max(mx[1]-mx[que[l]],mx[que[r]]));}for(int i1;in;i) if(isdia[i]) dfs2(i,0,0);printf(%d\n,ans);//fclose(stdin);//fclose(stdout);return 0;
} CF372C Watching Fireworks is Fun $\texttt{solution}$ 状态设 \(dp[i][j]\) 表示在放第 \(i\) 个烟花的时候在第 \(j\) 个位置的最大快乐值 。 转移方程 \[j-(t[i]-t[i-1])\times d\le k\le j(t[i]-t[i-1])\times d \]\[dp[i][j]\max{\{dp[i-1][k]b[i]-\operatorname{abs}(a[i]-j)\}} \]将转移方程变形 \[dp[i][j]b[i]-\operatorname{abs}(a[i]-j)\max{\{dp[i-1][k]\}} \]一看到上面这个方程一眼就会想到 单调队列优化\(\operatorname{DP}\) 可以用一个单调队列维护 \(dp[i-1][j-(t[i]-t[i-1]),j(t[i]-t[i-1])]\) 的最大值转移到 \(dp[i][j]\) 转移均摊 \(O(1)\) 。 复杂度\(O(nm)\) 。 代码 #includebits/stdc.h
using namespace std;
#define infll 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define Maxn 150005
#define Maxm 305
typedef long long ll;
inline ll rd()
{ll x0;char ch,t0;while(!isdigit(ch getchar())) t|ch-;while(isdigit(ch)) xx*10(ch^48),chgetchar();return xt?-x:x;
}
ll maxll(ll x,ll y){ return xy?x:y; }
ll minll(ll x,ll y){ return xy?x:y; }
ll absll(ll x){ return x0ll?x:-x; }
ll n,m,d,l,r,pos,que[Maxn];
ll p,ans-infll,a[Maxm],b[Maxm],t[Maxm],f[Maxn],g[Maxn];
int main()
{//freopen(.in,r,stdin);//freopen(.out,w,stdout);nrd(),mrd(),drd();for(ll i1;im;i) a[i]rd(),b[i]rd(),t[i]rd();for(ll i1;im;i){l1,r0,pos1,p(t[i]-t[i-1])*d;for(ll j1;jn;j){for(;posminll(n,jp);pos){while(lr g[que[r]]g[pos]) r--;que[r]pos;}while(lr que[l]j-p) l;f[j]g[que[l]]b[i]-absll(a[i]-j);}memcpy(g,f,sizeof(f));}for(ll i1;in;i) ansmaxll(ans,f[i]);printf(%lld\n,ans);//fclose(stdin);//fclose(stdout);return 0;
} 烧桥计划 $\texttt{solution}$ 题意 给你长为 \(n\) 的序列 \(a_1,a_2,\cdots,a_n\) 和一个参数 \(m\)。 删掉其中若干个位置 \(p_1,p_2,\cdots,p_k\) 耗费 \(\sum_{i1}^{k}i\cdot a_{p_i}\) 的代价将序列分为 \(k\) 段。 再对每段求和若 \(sum_km\) 则需额外支付 \(sum_k\) 的代价。求最小总代价。 \(n\leq 10^5,1000\leq a_i \leq 2000\) 。 题解 \(step~1\) 列出基础转移方程 。 状态设 \(dp[i][j]\) 表示前 \(i\) 个位置中选择删去了 \(j\) 个点其中第 \(i\) 个点强制删去的最小代价。可以通过在序列最后增加一个 \(0\) 使 \(\min{\{dp[n1][i]\}}\) 变为答案 。 转移( \(sum\) 表示前缀和 ) \[dp[i][j]\min{\{dp[k-1][j]calc(i-1,k)\}}j\times a[i] \]\(calc(i,j)\) 表示从 \(j1\) 到 \(i\) 的代价 。 \[calc(i,j)[sum[i]-sum[j]m]\times (sum[i]-sum[j]) \]通过枚举 \(i~j~k\) 复杂度为 \(O(n^3)\) 。 \(step~2\) 观察数据范围如果一个点都不删最大代价为 \(2000\times n\) 如果删除 \(k\) 个点最小代价为 \(1000\times \dfrac{k(k1)}{2}\) 。 因此 \(\texttt{选择删除的点数}\le 2\sqrt{n}\) ( \(j\le 2\sqrt{n}\) ) 。 \(step~3\) 将数组滚动省去 \(j\) 那一维转移最多进行 \(2\sqrt{n}\) 次 。 转移可以由两部分组成 \(calc(i-1,k)0\) 即 \(calc(i-1,k)sum[i-1]-sum[k]\) 。 则 \(dp[i][opt]\min{\{dp[k][opt\oplus1]-sum[k]\}}s[i-1]\) 可以在每一次 \(i\) 增加的时候更新 \(k\) 值并在更新的时候记录最小的 \(dp[k][opt\oplus1]-sum[k]\) ( 记为 \(tmp1\) )。 \(calc(i-1,k)0\) 则 \(dp[i][opt]\min{\{dp[k][opt\oplus1]\}}\) 可以用单调队列来维护这个最小值( 记为 \(tmp2\) ) 。 最终的 \(dp[i][opt]\min{(tmp1sum[i-1],tmp2)}j \times a[i]\) 。 时间复杂度\(O(n\sqrt{n})\) 。 核心代码 struct Data{ ll val,num; }q[Maxn];nrd(),mrd(),lim2*(sqrt(n)1);
for(ll i1;in;i) a[i]rd(),sum[i]sum[i-1]a[i];
a[n]0,sum[n]sum[n-1];
memset(dp,inf,sizeof(dp)),dp[0][0]dp[0][1]0;
for(ll i1;in;i) dp[i][opt]sum[i-1]m?sum[i]:a[i];
ansdp[n][opt];
for(ll k2;klim;k)
{opt^1;ll l1,r0,id0,tmpinfll;for(ll i1;in;i){while(sum[i-1]-sum[id]m) tmpminll(tmp,dp[id][opt^1]-sum[id]);while(lr q[l].numid) l;dp[i][opt]minll(tmpsum[i-1],q[l].val)k*a[i];while(lr q[r].valdp[i][opt^1]) r--;q[r](Data){dp[i][opt^1],i};}ansmin(ans,dp[n][opt]);
}
printf(%lld\n,ans); P2254 [NOI2005]瑰丽华尔兹 $\texttt{solution}$ \(step~1\) 考虑首先考虑对于时间 \(t\) 来 \(dp\) 状态设 \(dp[t][i][j]\) 表示在第 \(t\) 时刻在第 \(i\) 行第 \(j\) 列所能获得的最长距离 。 转移( \(pre_i\) 、\(pre_j\) 为上一个合法的位置) \[dp[t][i][j]\max{\{dp[t-1][i][j],dp[t-1][pre_i][pre_j]1\}} \]时间复杂度\(O(TN^2)\) 。 核心代码 for(int i1;ik;i) l[i]rd(),r[i]rd(),d[i]rd()-1;
memset(dp,-inf,sizeof(dp)),dp[0][sx][sy]0;
for(int t1,p1;tr[k];t)
{if(tr[p]) p;for(int i1;in;i) for(int j1;jm;j) if(mp[i][j].){int lxi-zou[d[p]][0],lyj-zou[d[p]][1];dp[t][i][j]max(dp[t-1][i][j],dp[t-1][lx][ly]1);}
}
for(int i1;in;i) for(int j1;jm;j) ansmax(ans,dp[r[k]][i][j]);
printf(%d\n,ans); \(step~2\) 把时间 \(t\) 换成区间 \(k\) 状态\(dp[k][i][j]\) 表示在第 \(k\) 段滑行区间中在位置 \(i\) \(j\) 所能获得最长距离 。 注意到在第 \(k\) 段时间内只能向某个方向最多走 \(x\) 步( \(x\) 为区间长度 )得到转移方程 \[dp[k][i][j]\max{\{dp[k-1][i][j],dp[k][pre_i][pre_j]dis(i,j,pre_i,pre_j)\}} \]时间复杂度\(O(KN^3)\) 。 核心代码 for(int i1;ik;i) l[i]rd(),r[i]rd(),d[i]rd()-1;
memset(dp,-inf,sizeof(dp)),dp[0][sx][sy]0;
for(int p1;pk;p)
{int addxzou[d[p]][0],addyzou[d[p]][1];for(int i1;in;i) for(int j1;jm;j) if(mp[i][j].){for(int lxi,lyj,add0;mp[lx][ly]. addr[p]-l[p]1;lx-addx,ly-addy,add)dp[p][i][j]max(dp[p][i][j],max(dp[p-1][i][j],dp[p-1][lx][ly]add));}
}
for(int i1;in;i) for(int j1;jm;j) ansmax(ans,dp[k][i][j]);
printf(%d\n,ans); \(step~3\) 加上 单调队列 和 滚动数组 优化 。 怎样单调队列对于第 \(i\) 段区间钢琴移动的方向即行(列)在每一列(行)都做一遍单调队列相当于快速求出了在第 \(i\) 段区间结束后的最优值 。 用单调队列求最优值的时候可以用偏移量( \(pos\) )来快速计算两个点之间的距离并且在遇到障碍块的时候清空队列 。 时间复杂度\(O(TN^2)\) 空间复杂度\(O(N^2)\) 。 核心代码 struct que{ int val,pos; }q[Maxn];
bool ok(int x,int y)
{if(x1 || xn || y1 || ym) return false;return true;
}
void solve(int sx,int sy,int len,int addx,int addy)
{int l1,r0;for(int txsx,tysy,cnt1;ok(tx,ty);txaddx,tyaddy,cnt){if(mp[tx][ty]x) l1,r0;else{while(lr q[r].valcnt-q[r].posdp[tx][ty]) r--;q[r](que){dp[tx][ty],cnt};while(lr cnt-q[l].poslen) l;dp[tx][ty]max(dp[tx][ty],q[l].valcnt-q[l].pos);}}
}memset(dp,-inf,sizeof(dp)),dp[sx][sy]0;
for(int p1;pk;p)
{int lrd(),rrd(),drd(),lenr-l1;if(d1) for(int i1;im;i) solve(n,i,len,-1,0);if(d2) for(int i1;im;i) solve(1,i,len,1,0);if(d3) for(int i1;in;i) solve(i,m,len,0,-1);if(d4) for(int i1;in;i) solve(i,1,len,0,1);
}
for(int i1;in;i) for(int j1;jm;j) ansmax(ans,dp[i][j]);
printf(%d\n,ans); P2569 [SCOI2010]股票交易 $\texttt{solution}$ \(step~1\) 先列出基础的转移方程比较容易想到。 状态设 \(dp[i][j]\) 表示到第 \(i\) 天拥有 \(j\) 分股票的最大收益(可能为负)。 转移暴力枚举 \(pre_i,pre_j\) 进行转移。 核心代码 trd(),mprd(),wrd();
for(int i1;it;i) pa[i]rd(),pb[i]rd(),sa[i]rd(),sb[i]rd();
memset(dp,-inf,sizeof(dp)),dp[0][0]0;
for(int i1;it;i) for(int j0;jmp;j) for(int pi0;pii-w-1;pi){for(int pjmax(j-sa[i],0);pjj;pj)dp[i][j]max(dp[i][j],dp[pi][pj]-pa[i]*(j-pj));for(int pjj1;pjmin(jsb[i],mp);pj)dp[i][j]max(dp[i][j],dp[pi][pj]pb[i]*(pj-j));}
for(int i0;it;i) for(int j0;jmp;j) ansmax(ans,dp[i][j]);
printf(%d\n,ans); 复杂度\(O(n^2Maxp^2)\) 。 \(step~2\) 可以发现 \(dp[i][j]\) 只会从 \(dp[i-w-1][\dots]\) 转移过来因为 \(dp[i-w-1][\dots]\) 已经是当时的最优决策。 注意进行一系列初始化 (合法情况下) \(dp[i][j]-pa[i]\times j\) 。 \(dp[i][j]\max{\{dp[i][j],dp[i-1][j]\}}\) (不转移) 。 \(dp[i][j]\max{\{dp[i][j],dp[i-w-1][\dots]\dots\}}\) (进行交易)。 核心代码 trd(),mprd(),wrd();
for(int i1;it;i) pa[i]rd(),pb[i]rd(),sa[i]rd(),sb[i]rd();
memset(dp,-inf,sizeof(dp)),dp[0][0]0;
for(int i1;it;i) for(int j0;jsa[i];j) dp[i][j]-pa[i]*j;
for(int i1;it;i) for(int j0;jmp;j){dp[i][j]max(dp[i][j],dp[i-1][j]);int pii-w-1;if(pi0) continue;for(int pjmax(j-sa[i],0);pjj;pj)dp[i][j]max(dp[i][j],dp[pi][pj]-pa[i]*(j-pj));for(int pjj1;pjmin(jsb[i],mp);pj)dp[i][j]max(dp[i][j],dp[pi][pj]pb[i]*(pj-j));}
for(int i0;it;i) for(int j0;jmp;j) ansmax(ans,dp[i][j]);
printf(%d\n,ans); 复杂度 \(O(nMaxp^2)\) 。 \(step~3\) 发现在 for(int pjmax(j-sa[i],0);pjj;pj)dp[i][j]max(dp[i][j],dp[pi][pj]-pa[i]*(j-pj));
for(int pjj1;pjmin(jsb[i],mp);pj)dp[i][j]max(dp[i][j],dp[pi][pj]pb[i]*(pj-j)); 中可以用单调队列进行优化然后就做完了 。 核心代码 trd(),mprd(),wrd();
for(int i1;it;i) pa[i]rd(),pb[i]rd(),sa[i]rd(),sb[i]rd();
memset(dp,-inf,sizeof(dp)),dp[0][0]0;
for(int i1;it;i) for(int j0;jsa[i];j) dp[i][j]-pa[i]*j;
for(int i1;it;i)
{int pii-w-1;for(int j0;jmp;j) dp[i][j]max(dp[i][j],dp[i-1][j]);if(pi0) continue;for(int j1,l1,r0;jmp;j){while(lr q[l]j-sa[i]) l;while(lr dp[pi][q[r]]pa[i]*q[r]dp[pi][j-1]pa[i]*(j-1)) r--;q[r]j-1;dp[i][j]max(dp[i][j],dp[pi][q[l]]pa[i]*q[l]-pa[i]*j);}for(int jmp-1,l1,r0;j0;j--){while(lr q[l]jsb[i]) l;while(lr dp[pi][q[r]]pb[i]*q[r]dp[pi][j1]pb[i]*(j1)) r--;q[r]j1;dp[i][j]max(dp[i][j],dp[pi][q[l]]pb[i]*q[l]-pb[i]*j);}
}
for(int i0;it;i) for(int j0;jmp;j) ansmax(ans,dp[i][j]);
printf(%d\n,ans); 复杂度 \(O(nMaxp)\) 可以通过此题 。 P2300 合并神犇 $\texttt{solution}$ 题意将 \(n\) 个数分为若干组使每一组所有数的和 \(\ge\) 上一组所有数的和求最大分组数。(几乎同 CSP2019 Day2T1) 考虑处理到第 \(i\) 个数设 \(d[i]\) 表示在这个局部解中合并了 \(i-d[i]1\) 至 \(i\) 则转移方程为 \[dp[i]\max_{ji~\land~d[j]\le sum[i]-sum[j1]} \{dp[j]1\} \]使用单调队列维护最大值。 代码 (变式改为每一组所有数的和 \(\le\) 上一组所有数的和。将 \(\{a\}\) 翻转即可)
