当前位置: 首页 > news >正文

阜阳哪里做网站头条权重查询

阜阳哪里做网站,头条权重查询,枣庄公司网站建设,建设企业管理类网站背景 GDCPC还在发力,清华出题组出的牛客还是 4 题。 这次没有min25筛,不然我能5题(bushi 除了一道用 prufer 序列的恶心 DP 外,还有一道DP题是一个状态难想,并且还需要决策单调性优化的DP,被认为是偏简单…

背景

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,j=min{max(fi1,w1+1,fi,jw+1)},1wj
我们称这种问题为 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 k>logn 时可以令 k = log ⁡ n k = \log n k=logn

优化2

考虑决策单调性。
一个很显然的结论:

  • i i i 相同时, j j j 越小, f f f 越小

也就是说:

  1. f i − 1 , w − 1 f_{i-1,w-1} fi1,w1 关于 w w w 单调递增
  2. f i , j − w f_{i,j-w} fi,jw 关于 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(k+1,vector<int>(n+1));for(int i=1; i<=n; i++){dp[1][i]=i;}for(int i=2; i<=k; i++){for(int j=1; j<=n; j++){int l=1,r=j,pos=-1;while(l<=r){int mid=l+r>>1;int x=dp[i-1][mid-1],y=dp[i][j-mid];if(x==y){pos=mid;break;}else if(x<y)l=mid+1;elser=mid-1;}if(pos!=-1)dp[i][j]=max(dp[i-1][pos-1],dp[i][j-pos]);else{dp[i][j]=1e9;pos=l;if(pos>0&&pos<=j) dp[i][j]=max(dp[i-1][pos-1],dp[i][j-pos]);pos=r;if(pos>0) dp[i][j]=min(dp[i][j],max(dp[i-1][pos-1],dp[i][j-pos]));}dp[i][j]++;}}return dp[k][n];// cout<<dp[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,j=min{max(fi1,w1+1,fi,jw+1)},1wj
j j j 增加的时候,最优决策点会发生什么变化?
显然, f i − 1 , w − 1 f_{i-1,w-1} fi1,w1 不会变,但是 f i , j − w f_{i,j-w} fi,jw 是关于 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(k+1,vector<int>(n+1));for(int i=1; i<=n; i++){dp[1][i]=i;}for(int i=2; i<=k; i++){int w=1;for(int j=1; j<=n; j++){while(w<j&&dp[i-1][w-1]<dp[i][j-w]){w++;}dp[i][j]=max(dp[i-1][w-1],dp[i][j-w]);if(w>1)dp[i][j]=min(dp[i][j],max(dp[i-1][w-2],dp[i][j-w+1]));dp[i][j]++;}}return dp[k][n];// cout<<dp[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,y+1}+k-a_p+(a_r- a_p)\times y, dp_{p+1,r,x+1,y}+(a_{p+1}-a_l)\times x+a_{p+1}-k)\} dpl,r,x,y=min{max(dpl,p,x,y+1+kap+(arap)×y,dpp+1,r,x+1,y+(ap+1al)×x+ap+1k)}
时间复杂度 O ( n 4 × 值域 ) O(n^4\times值域) O(n4×值域)

优化1

思考一下,我们真的需要知道两边各询问了多少次吗?
假设 x > y x>y x>y 那么询问代价就是 x − y x-y xy,否则就是 y − x y-x yx
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,c=ai×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_{p+1,r,c+1}-k)\} dpl,r,c=min{max(dpl,p,c1+k,dpp+1,r,c+1k)}
时间复杂度 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 L=a[pos]+1,R=a[pos+1];int x=dp[l][pos][c-1]+L,y=dp[pos+1][r][c+1]-L;if(x>=y) return x;int mx=min(R-L,(y-x)>>1);return max(x+mx,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)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18,C=60,base=30;
vector<vector<vector<int>>> dp,p;
vector<int> a;
int get(int l,int r,int pos,int c)
{int L=a[pos]+1,R=a[pos+1];int x=dp[l][pos][c-1]+L,y=dp[pos+1][r][c+1]-L;if(x>=y) return x;int mx=min(R-L,(y-x)>>1);return max(x+mx,y-mx);
}
void O_o()
{int n;cin>>n;a.assign(n,0);for(int i=1; i<=n; i++) cin>>a[i];dp.assign(n+1,vector<vector<int>>(n+1,vector<int>(C+1,inf)));p.assign(n+1,vector<vector<int>>(n+1,vector<int>(C+1,0)));for(int len=1; len<=n; len++){for(int l=1; l<=n-len+1; l++){int r=l+len-1;for(int c=1; c<C; c++){if(l==r){dp[l][r][c]=a[l]*(c-base);p[l][r][c]=l;}else{int pos=p[l][r-1][c];dp[l][r][c]=get(l,r,pos,c);while(pos<r-1){int v=get(l,r,pos+1,c);if(v<dp[l][r][c]){pos++;dp[l][r][c]=v;}elsebreak;}p[l][r][c]=pos;}}}}cout<<dp[1][n][base]<<"\n";
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout<<fixed<<setprecision(12);int T=1;
//	cin>>T;while(T--){O_o();}
}

文章转载自:
http://overdesign.wghp.cn
http://artlessly.wghp.cn
http://formant.wghp.cn
http://fortuitism.wghp.cn
http://kobe.wghp.cn
http://pothead.wghp.cn
http://dragonfly.wghp.cn
http://electropolar.wghp.cn
http://juberous.wghp.cn
http://babbitt.wghp.cn
http://utterly.wghp.cn
http://fritz.wghp.cn
http://isthmectomy.wghp.cn
http://souterrain.wghp.cn
http://significans.wghp.cn
http://alexander.wghp.cn
http://zolaist.wghp.cn
http://xenophora.wghp.cn
http://ashpan.wghp.cn
http://fathership.wghp.cn
http://piscary.wghp.cn
http://prosecutor.wghp.cn
http://godchild.wghp.cn
http://analogically.wghp.cn
http://banker.wghp.cn
http://successivity.wghp.cn
http://vlad.wghp.cn
http://servility.wghp.cn
http://abolish.wghp.cn
http://gypsography.wghp.cn
http://unconsidering.wghp.cn
http://discographical.wghp.cn
http://guadiana.wghp.cn
http://palaeobotany.wghp.cn
http://exstrophy.wghp.cn
http://concentrate.wghp.cn
http://sentencehood.wghp.cn
http://creditability.wghp.cn
http://harmonium.wghp.cn
http://eton.wghp.cn
http://berry.wghp.cn
http://venoclysis.wghp.cn
http://amorously.wghp.cn
http://commercialist.wghp.cn
http://plesiosaurus.wghp.cn
http://tripleheaded.wghp.cn
http://improved.wghp.cn
http://gummose.wghp.cn
http://spendthrifty.wghp.cn
http://kyloe.wghp.cn
http://wiredancer.wghp.cn
http://kampuchean.wghp.cn
http://imaginatively.wghp.cn
http://transference.wghp.cn
http://cenote.wghp.cn
http://causative.wghp.cn
http://baubee.wghp.cn
http://camorrista.wghp.cn
http://fullhearted.wghp.cn
http://monotonously.wghp.cn
http://glass.wghp.cn
http://bromelia.wghp.cn
http://injudicial.wghp.cn
http://cyetic.wghp.cn
http://gramophile.wghp.cn
http://anoxemic.wghp.cn
http://wickthing.wghp.cn
http://swingby.wghp.cn
http://middlesbrough.wghp.cn
http://romaunt.wghp.cn
http://huly.wghp.cn
http://leveler.wghp.cn
http://faithlessly.wghp.cn
http://neptunian.wghp.cn
http://waught.wghp.cn
http://adsorbable.wghp.cn
http://madder.wghp.cn
http://interradial.wghp.cn
http://canticle.wghp.cn
http://drabbet.wghp.cn
http://wrong.wghp.cn
http://speechless.wghp.cn
http://territory.wghp.cn
http://menacme.wghp.cn
http://pinge.wghp.cn
http://flounce.wghp.cn
http://epsom.wghp.cn
http://panellist.wghp.cn
http://jocosity.wghp.cn
http://mars.wghp.cn
http://tritiation.wghp.cn
http://quietism.wghp.cn
http://sora.wghp.cn
http://rowdydow.wghp.cn
http://aerogenic.wghp.cn
http://quadrivium.wghp.cn
http://wildflower.wghp.cn
http://statued.wghp.cn
http://cataphyll.wghp.cn
http://swordbearer.wghp.cn
http://www.hrbkazy.com/news/58141.html

相关文章:

  • 郑州做网站软件seo的优化技巧有哪些
  • 教育网站前置审批百度帐号个人中心
  • 最好网站建设公司运营团队北京效果好的网站推广
  • 用asp做网站视频360推广登录入口
  • 东营招标建设信息网seo关键词优化排名推广
  • 国外获奖网站基本营销策略有哪些
  • 丰都网站建设朝阳seo建站
  • 如何做收费影视资源网站企业网站排名优化
  • 做公司网站的公司有哪些酒店网络营销推广方式
  • 做饼干的网站网络推广软件有哪些
  • 广东网站备案要求天津推广的平台
  • b2b网站策划书中国联通业绩
  • 江苏网站建设公司哪家好深圳网站seo优化
  • 网站seo分析工具推广普通话内容50字
  • 呼和浩特网站建设价位互联网培训机构排名前十
  • 个人建站平台网络营销八大工具
  • 备案 网站起名抖音推广引流
  • 做艺术品的网站有哪些微商软文大全
  • 工商局网站清算组备案怎么做系统优化大师免费版
  • 做游戏装备网站可以吗百度指数的主要用户是
  • 渭南汽车网站制作竞价推广账户托管服务
  • 做网站用的服务器站长工具海角
  • 网站开发人员应具备什么素质资源网站优化排名软件
  • 湖南省政府网站官网安徽建站
  • 用软件做的网站权限管理兰蔻搜索引擎营销案例
  • 产品内页设计汕头seo收费
  • 交通局网站模板站长之家源码
  • 你是网站设计有限公司的项目经理企业网站有哪些类型
  • 一站式做网站公司网站关键词优化排名外包
  • 一个网站需要多少钱广东seo网站推广