小工作室做网站,网站前端制作费用,网站头图设计,自我介绍网站html背景
GDCPC还在发力#xff0c;清华出题组出的牛客还是 4 题。 这次没有min25筛#xff0c;不然我能5题#xff08;bushi
除了一道用 prufer 序列的恶心 DP 外#xff0c;还有一道DP题是一个状态难想#xff0c;并且还需要决策单调性优化的DP#xff0c;被认为是偏简单…背景
GDCPC还在发力清华出题组出的牛客还是 4 题。 这次没有min25筛不然我能5题bushi
除了一道用 prufer 序列的恶心 DP 外还有一道DP题是一个状态难想并且还需要决策单调性优化的DP被认为是偏简单的银牌题。
先来看个相对简单的问题
鸡蛋掉落 这是一道非常经典的面试题。本博客不会介绍这题的最优方法时间复杂度 O ( n ) O(\sqrt n) O(n )
暴力DP
设 f i , j f_{i,j} fi,j 为还剩 i i i 个鸡蛋楼高 j j j 层需要的最少实验次数。 显然有转移 f i , j min { max ( f i − 1 , w − 1 1 , f i , j − w 1 ) } , 1 ≤ w ≤ j f_{i,j} \min\{\max (f_{i-1,w-1}1,f_{i,j-w}1)\}, 1 \leq w \leq j fi,jmin{max(fi−1,w−11,fi,j−w1)},1≤w≤j 我们称这种问题为 m i n m a x minmax minmax 问题 时间复杂度 O ( k n log n ) O(kn\log n) O(knlogn)
优化1
显然如果鸡蛋足够多我们可以直接二分出高度。所以当 k log n k\log n klogn 时可以令 k log n k \log n klogn
优化2
考虑决策单调性。 一个很显然的结论 i i i 相同时 j j j 越小 f f f 越小
也就是说 f i − 1 , w − 1 f_{i-1,w-1} fi−1,w−1 关于 w w w 单调递增 f i , j − w f_{i,j-w} fi,j−w 关于 w w w 单调递减
所以两个函数值的关系如图
我们的最优决策点在红色点那里。显然这玩意可以二分。 时间复杂度 O ( n log 2 n ) O(n \log ^2 n) O(nlog2n)
class Solution {
public:int superEggDrop(int k, int n) {vector dp(k1,vectorint(n1));for(int i1; in; i){dp[1][i]i;}for(int i2; ik; i){for(int j1; jn; j){int l1,rj,pos-1;while(lr){int midlr1;int xdp[i-1][mid-1],ydp[i][j-mid];if(xy){posmid;break;}else if(xy)lmid1;elsermid-1;}if(pos!-1)dp[i][j]max(dp[i-1][pos-1],dp[i][j-pos]);else{dp[i][j]1e9;posl;if(pos0posj) dp[i][j]max(dp[i-1][pos-1],dp[i][j-pos]);posr;if(pos0) dp[i][j]min(dp[i][j],max(dp[i-1][pos-1],dp[i][j-pos]));}dp[i][j];}}return dp[k][n];// coutdp[k][n]\n;}
};优化3
回到DP式子 f i , j min { max ( f i − 1 , w − 1 1 , f i , j − w 1 ) } , 1 ≤ w ≤ j f_{i,j} \min\{\max (f_{i-1,w-1}1,f_{i,j-w}1)\}, 1 \leq w \leq j fi,jmin{max(fi−1,w−11,fi,j−w1)},1≤w≤j 当 j j j 增加的时候最优决策点会发生什么变化 显然 f i − 1 , w − 1 f_{i-1,w-1} fi−1,w−1 不会变但是 f i , j − w f_{i,j-w} fi,j−w 是关于 j j j 单调递增的。 不难想象那个红色的点就会往右边走。也就说最优决策点也满足单调性当 j j j 右移时最优的 w w w 也右移。 所以我们可以用双指针代替二分。
时间复杂度 O ( n log n ) O(n\log n) O(nlogn) class Solution {
public:int superEggDrop(int k, int n) {vector dp(k1,vectorint(n1));for(int i1; in; i){dp[1][i]i;}for(int i2; ik; i){int w1;for(int j1; jn; j){while(wjdp[i-1][w-1]dp[i][j-w]){w;}dp[i][j]max(dp[i-1][w-1],dp[i][j-w]);if(w1)dp[i][j]min(dp[i][j],max(dp[i-1][w-2],dp[i][j-w1]));dp[i][j];}}return dp[k][n];// coutdp[k][n]\n;}
};其实还有一种很好的写法是
先用当前决策点更新 d p dp dp 值如果决策点右移可以使 d p dp dp 值更优就继续往右移并更新 d p dp dp 值否则就 b r e a k break break
2024牛客暑期多校训练营5 K 暴力
最暴力的想法是区间DP设 d p l , r dp_{l,r} dpl,r 为已经把答案范围缩小到 [ a l , a r ] [a_l,a_r] [al,ar]还需要多少代价才能确定答案。 但你很快会发现没办法直接区间DP因为你根本不知道 x x x 在哪。 但是如果我们知道之前我左边问过多少次右边问过多少次就可以计算区间扩展产生的代价。 所以我们可以设 d p i , j , x , y dp_{i,j,x,y} dpi,j,x,y 代表已经把答案范围缩小到 [ a l , a r ] [a_l,a_r] [al,ar]之前在区间左边问了 x x x 次右边问了 y y y 次还需要多少代价。
转移就可以枚举中间点 k k k令分割点为 p p p那么转移就是 d p l , r , x , y min { max ( d p l , p , x , y 1 k − a p ( a r − a p ) × y , d p p 1 , r , x 1 , y ( a p 1 − a l ) × x a p 1 − k ) } dp_{l,r,x,y} \min\{\max(dp_{l,p,x,y1}k-a_p(a_r- a_p)\times y, dp_{p1,r,x1,y}(a_{p1}-a_l)\times xa_{p1}-k)\} dpl,r,x,ymin{max(dpl,p,x,y1k−ap(ar−ap)×y,dpp1,r,x1,y(ap1−al)×xap1−k)} 时间复杂度 O ( n 4 × 值域 ) O(n^4\times值域) O(n4×值域)
优化1
思考一下我们真的需要知道两边各询问了多少次吗 假设 x y xy xy 那么询问代价就是 x − y x-y x−y否则就是 y − x y-x y−x y y y 的代价可以在DP转移的时候直接记录 x x x 的代价当 x x x 确定下来的时候可以通过 左边询问次数 - 右边询问次数 来计算 所以其实我们只需记录三四维的差值就行。
设 d p l , r , c dp_{l,r,c} dpl,r,c 代表已经把答案范围缩小到 [ a l , a r ] [a_l,a_r] [al,ar]之前在区间左边和右边询问次数之差为 c c c 次 x x x 的全局代价计算 还需要的代价。 显然初始化为 d p i , i , c a i × c dp_{i,i,c} a_i\times c dpi,i,cai×c
同样的转移就可以枚举中间点 k k k令分割点为 p p p那么转移就是 d p l , r , c min { max ( d p l , p , c − 1 k , d p p 1 , r , c 1 − k ) } dp_{l,r,c} \min\{\max(dp_{l,p,c-1}k, dp_{p1,r,c1}-k)\} dpl,r,cmin{max(dpl,p,c−1k,dpp1,r,c1−k)} 时间复杂度 O ( n 3 × 值域 ) O(n^3\times 值域) O(n3×值域)
优化2
可证明 c c c 不会超过 O ( log n ) O(\log n) O(logn) 个我不会证 时间复杂度 O ( n 2 log n × 值域 ) O(n^2\log n\times 值域) O(n2logn×值域)
优化3
首先值域那玩意大的离谱。但是从 d p dp dp 式子很容易看出来一个 k k k 一个 − k -k −k显然是有单调性的 k k k 的决策点可以 O ( 1 ) O(1) O(1) 求
int get(int l,int r,int pos,int c)
{int La[pos]1,Ra[pos1];int xdp[l][pos][c-1]L,ydp[pos1][r][c1]-L;if(xy) return x;int mxmin(R-L,(y-x)1);return max(xmx,y-mx);
}时间复杂度 O ( n 3 log n ) O(n^3\log n) O(n3logn)
优化4
现在时间复杂度的瓶颈在于枚举 p p p怎么把这玩意优化掉呢 当区间左端点不动右端点增加的时候显然方程的第一项是不变的第二项是单调递减的。这个时候把 p p p 往右移动可以让第一项减小第二项增大。所以最优决策点 p p p 会关于 r r r 单调递增我们同样可以用双指针来处理决策点。 时间复杂度 O ( n 2 log n ) O(n^2\log n) O(n2logn)
代码
#includebits/stdc.h
#define int long long
using namespace std;
const int N1e67,inf1e18,C60,base30;
vectorvectorvectorint dp,p;
vectorint a;
int get(int l,int r,int pos,int c)
{int La[pos]1,Ra[pos1];int xdp[l][pos][c-1]L,ydp[pos1][r][c1]-L;if(xy) return x;int mxmin(R-L,(y-x)1);return max(xmx,y-mx);
}
void O_o()
{int n;cinn;a.assign(n,0);for(int i1; in; i) cina[i];dp.assign(n1,vectorvectorint(n1,vectorint(C1,inf)));p.assign(n1,vectorvectorint(n1,vectorint(C1,0)));for(int len1; lenn; len){for(int l1; ln-len1; l){int rllen-1;for(int c1; cC; c){if(lr){dp[l][r][c]a[l]*(c-base);p[l][r][c]l;}else{int posp[l][r-1][c];dp[l][r][c]get(l,r,pos,c);while(posr-1){int vget(l,r,pos1,c);if(vdp[l][r][c]){pos;dp[l][r][c]v;}elsebreak;}p[l][r][c]pos;}}}}coutdp[1][n][base]\n;
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);coutfixedsetprecision(12);int T1;
// cinT;while(T--){O_o();}
}
