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

wordpress 修改文章id/seo优化多少钱

wordpress 修改文章id,seo优化多少钱,龙岩市住房与城乡建设部网站,用java做的网站有哪些内容题意 Farmer John 饲养了 N N N 种奶牛,编号从 1 1 1 到 N N N。一些品种的奶牛和其他奶牛间相处良好,事实证明,如果两个品种的奶牛编号分别为 a , b a,b a,b,当 ∣ a − b ∣ ≤ 4 |a-b| \leq 4 ∣a−b∣≤4 时&#xff0c…

题意

Farmer John 饲养了 N N N 种奶牛,编号从 1 1 1 N N N。一些品种的奶牛和其他奶牛间相处良好,事实证明,如果两个品种的奶牛编号分别为 a , b a,b a,b,当 ∣ a − b ∣ ≤ 4 |a-b| \leq 4 ab4 时,这两个品种的奶牛能友好相处,否则不能友好相处。

一条长长的道路贯穿整个农场,道路的左侧有 N N N 个牧场(每个品种的奶牛恰好占据一个牧场),道路的右侧也有 N N N 个牧场(每个品种的奶牛恰好占据一个牧场)。为了让奶牛们安全穿过马路,Farmer John 希望能在马路上画出一些人行道(牛行道?),要求这些人行道满足如下条件:

  1. 人行道从左侧的某个牧场出发,连接到右侧的某个牧场;
  2. 人行道连接的两个牧场的奶牛要能友好相处;
  3. 人行道不能在道路中间相交;
  4. 每个牧场只能与一条人行道相连。

你需要帮 FJ 求出最多能有多少条人行道。

洛谷 P6119: 1 ≤ n ≤ 1000 1\le n\le 1000 1n1000:;

洛谷 P3657: 1 ≤ n ≤ 1 0 5 1\le n\le 10^5 1n105

本题解两个数据范围有不同解法。

思路(小数据)

这个数据支持 Θ ( n 2 ) \Theta(n^2) Θ(n2)

我们考虑枚举两侧的道路进行匹配。而题目要求道路不能交叉,那么得“一起推进”——其实是 dp。

f i , j f_{i,j} fi,j 表示, a a a 数组前 i i i 个、 b b b 数组前 j j j 个的最大匹配数。

如果 ∣ a i − b j ∣ ≤ 4 |a_i-b_j|\le 4 aibj4,那么就可以在左侧的 i i i 和 右侧的 j j j 建立道路(在接下来就不会在出现,左侧小于 i i i 的连接右侧大于 j j j 的的道路了)。
在这里插入图片描述
f i , j = max ⁡ { f i − 1 , j − 1 + 1 } , ∣ a i − b j ∣ ≤ 4 f_{i,j}=\max\{f_{i-1,j-1}+1\},|a_i-b_j|\le 4 fi,j=max{fi1,j1+1},aibj4

否则就不能建,那么从哪里转移过来呢?跳过 i i i j j j 其中一个点不建边就好了。
在这里插入图片描述
f i , j = max ⁡ { f i − 1 , j , f i , j − 1 } f_{i,j}=\max\{f_{i-1,j},f_{i,j-1}\} fi,j=max{fi1,j,fi,j1}

代码 1

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1002; 
ll n,a[N],b[N];
ll f[N][N];
int main()
{scanf("%lld",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);for(int i=1;i<=n;i++)scanf("%lld",&b[i]);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){f[i][j]=max(f[i][j],max(max(f[i-1][j],f[i][j-1]),f[i-1][j-1]));if(abs(a[i]-b[j])<=4)f[i][j]=max(f[i][j],f[i-1][j-1]+1);}}printf("%lld",f[n][n]);return 0;
}

思路(大数据)

虽然很典型,但是还是思维有点混乱,这种节点贡献的题目还是要多练。

能否考虑优化小数据的做法呢?省去一个维度?

对每一个 a i a_i ai,枚举可以和它配对的种类区间 [ a i − 4 , a i + 4 ] [a_i-4,a_i+4] [ai4,ai+4]

省去一维,设 f i f_i fi 表示,当前,右侧的种类 i i i 对应点 p o s i pos_i posi 作为配对的结尾的最大匹配数,然后更新 p o s i pos_i posi 的贡献为 f i + 1 f_i+1 fi+1

考虑用树状数组维护。

代码 2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+9;
ll n,a[N],b[N],pos[N];//右位置 
ll f[N];
struct BT
{ll T[N];ll lowbit(ll x){return x&(-x);}void add(ll x,ll k){for(int i=x;i<=n;i+=lowbit(i))T[i]=max(T[i],k);}ll query(ll x){x=min(x,n),x=max(x,0ll);ll ret=0;for(int i=x;i>=1;i-=lowbit(i))ret=max(ret,T[i]);return ret;}
}B;
int main()
{scanf("%lld",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);for(int i=1;i<=n;i++){scanf("%lld",&b[i]);pos[b[i]]=i;}for(int i=1;i<=n;i++){//符合条件的品种区间 for(int j=max(a[i]-4,1ll);j<=min(a[i]+4,n);j++)f[j]=B.query(pos[j]-1);for(int j=max(a[i]-4,1ll);j<=min(a[i]+4,n);j++)B.add(pos[j],f[j]+1);}ll ans=B.query(n);printf("%lld",ans);return 0;
}
http://www.whsansanxincailiao.cn/news/30249408.html

相关文章:

  • css企业网站模板/郑州网站制作公司哪家好
  • 免费b网站推广/购物网站有哪些
  • 男女做啊免费视频网站/站内关键词自然排名优化
  • 西宁建设网站价格低/上海app网络推广公司
  • 哈尔滨门户网站设计报价/seo建站网络公司
  • 怎样用jsp做网站/企业网站设计论文
  • 做代理网站/商务软文写作范文200字
  • 做网站加入广告联盟/seo职业发展
  • 做网站好赚钱/广州seo优化费用
  • 衣服销售网站建设规划书范文/360收录
  • 廊坊seo外包公司/黑帽seo工具
  • 寿光网站建设定制/百度电脑网页版
  • 公司网站开发有哪些/巧克力软文范例200字
  • 专业网站开发哪里好/游戏代理加盟平台
  • 东莞网站建设 少儿托管/网络营销的重要性
  • mui做网站的好处/百度关键词seo排名优化
  • 中建卓越建设管理有限公司网站/上海网站推广服务公司
  • 省政府网站建设/搜什么关键词比较刺激
  • 可以先做网站后备案么/排名优化公司电话
  • 怎样做网站卖东西/百度公司招聘2022年最新招聘
  • 网站导航条模板/品牌推广软文200字
  • 墨刀做网站/百度竞价关键词优化
  • 初中生怎么提升学历/宁宁网seo
  • 网站建设分工说明/企业网络营销方法
  • 重庆seo网络推广优化/聊城seo培训
  • 用户体验差有哪些网站/百度平台营销软件
  • vultr 做网站空间/seo优化基础教程pdf
  • wordpress 插件 上传/佛山网站seo
  • 上海做网站品牌公司/竞价推广网络推广运营
  • 网站建设 科技公司/seo网址优化靠谱