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

寮步镇做网站百度客服平台

寮步镇做网站,百度客服平台,向公司申请建设网站申请书,门户网站设计欣赏本专题再介绍几种经典的字串问题。 这是一个两个不重叠字串和的问题,我们只要去枚举分界点c即可,我们不妨让c作为右区间的左边界,然后求[1,c)上的单个字串和并用max数组维护。对于右边,我们只要反向求单个字串和然后选左边界为c的…

本专题再介绍几种经典的字串问题。

这是一个两个不重叠字串和的问题,我们只要去枚举分界点c即可,我们不妨让c作为右区间的左边界,然后求[1,c)上的单个字串和并用max数组维护。对于右边,我们只要反向求单个字串和然后选左边界为c的一组即可。

下面是AC代码:

#include<stdio.h>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long t,a[50010],b[50010],max1[50010],n,ck[50010],hh;
int main(){scanf("%lld",&t);while(t--){memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(max1,0,sizeof(max1));scanf("%lld",&n);for(int i=1;i<=n;i++) scanf("%lld",&ck[i]);for(int i=1;i<=n;i++){if(i==1){a[i]=ck[i];max1[i]=ck[i];}else{a[i]=max(ck[i],ck[i]+a[i-1]);max1[i]=max(max1[i-1],a[i]);}}for(int i=n;i>=1;i--){if(i==n) b[i]=ck[i];else b[i]=max(ck[i],ck[i]+b[i+1]);}hh=-0x3f;for(int c=2;c<=n;c++){hh=max(hh,max1[c-1]+b[c]);}printf("%lld\n",hh);}
}

接下来,我们加点难度:

现在2变成了m,我们进行升维操作,我们令f[i][j]为前j个数(第j个数必须取)组成的i个不相交子段最大和。

当我们要从j-->j+1时,对于第j+1,它可以作为最后一个子段的末尾,也可以不做末尾而是起点,而此时我们要去得到i-1个不相交子段的max,因此,我们易得转移方程为:

f[i][j]=max(f[i][j-1]+a[j],f[i-1][k]+a[j])

复杂度为o(n^2*m)

我们考虑优化一下:

f[i][j]=a[j]+max(f[i][j-1],f[i-1][k]).

我们只要维护每一个点对应的一列上从上到下的max即可。

至于初始条件,0组的情况都为0(就比如m=1,有一种情况就是只选他自己,因此要赋0)

下面是AC代码(dp数组用滚动即可):

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000100],mmm;
int ans,dp[1000100];
int ck[1000100];
int main(){while(scanf("%d%d",&m,&n)!=EOF){ans=-0x3f;for(int i=1;i<=n;i++) scanf("%d",&a[i]);memset(dp,0,sizeof(dp));memset(ck,0,sizeof(ck));for(int i=1;i<=m;i++){mmm=-0x3f;for(int j=i;j<=n;j++){dp[j]=max(dp[j-1],ck[j-1])+a[j];ck[j-1]=mmm;mmm=max(mmm,dp[j]);}}printf("%d\n",mmm);	}
}

让我们再加点难度:如果是环状呢?

有一道石子合并的通过复制一份来解决,但是因为这个不能利用上一次划分的情况,换句话说,这一次每次断开都要重新求(原因在于不是区间dp),于是我们不妨想一想另一种方法:

我们知道假如n与1没有被当成一段取,跟上面的就一样了。

如果n与1被当成一段取,那么我们在n与1断开的时候就相当于要求m+1段区间,其中第一段必须包含第一个元素,最后一个必须包含最后一个元素。

下面是AC代码(呜呜呜,直接初值赋了-0x3f,结果当成16进制,检查了好久):

#include<bits/stdc++.h>
using namespace std;
int n,m,a[200100],mmm,mmm1;
int ans,dp[200100],dp1[200100];
int ck[200100],ck1[200100],hou[200100],maxx[200100];
int main(){scanf("%d",&n);ck1[0]=-10000000;ans=-10000000;for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) dp1[i]=a[i]+dp1[i-1];for(int i=1;i<=n;i++) ck1[i]=max(dp1[i],ck1[i-1]);for(int i=n;i>=1;i--) hou[i]=a[i]+hou[i+1];for(int i=n;i>=1;i--){if(i==n) maxx[i]=a[i];else maxx[i]=max(maxx[i+1],hou[i]);}for(int i=1;i<=2;i++){mmm=-10000000;for(int j=i;j<=n;j++){dp[j]=max(dp[j-1],ck[j-1])+a[j];ck[j-1]=mmm;mmm=max(mmm,dp[j]);}}mmm1=-10000000;for(int j=2;j<=n;j++){dp1[j]=max(dp1[j-1],ck1[j-1])+a[j];ck1[j-1]=mmm1;mmm1=max(mmm1,dp1[j]);}for(int i=2;i<=n-1;i++){ans=max(ans,dp1[i]+maxx[i+1]);}printf("%d\n",max(mmm,ans));	}

接下来,让我们再看看公共子序列问题吧:

我们以前也写过,我们把dp扩展成3维即可。

同时对于方案,我们一般用last数组记录上一次的情况,显然在这里就比较麻烦。我们可以用一个字符串,每次3个的最后一个元素相等时记录一下即可。

http://www.hrbkazy.com/news/55622.html

相关文章:

  • 蓝色大气网站欣赏网站怎么找
  • 如何查询网站的服务器百度登录首页
  • 青海公司网站建设哪家好免费有效的推广平台
  • 做优化的网站用什么空间好软文营销案例200字
  • 毕业设计网站开发泸州网站seo
  • 赣州网络台网站移动端优化工具
  • 深圳市seo上词贵不贵抖音搜索seo代理
  • 在县城做同城网站怎么样技能培训机构
  • 海阳网站制作获客
  • 网站建设登录注册怎么做关键词优化排名第一
  • 建设网站企业网上银行登录入口友情链接批量查询
  • 北京外贸网站建设全国人大常委会
  • 福州网站建设多少钱关键词点击排名软件
  • 中国建设劳动协会网站武汉大学人民医院精神科
  • 晋城网站制作公司怎么选最吸引人的营销广告文案
  • 08网站建设优化网站结构一般包括
  • 导购类网站如何做会员互动重庆seo整站优化外包服务
  • 福州外文网站建设国际最新消息
  • php做网站优势自动app优化最新版
  • 中文网页设计案例欣赏seo优化多久能上排名
  • 集团培训网站建设网站推广方案
  • 网站备案期间停止解析网络营销案例
  • 网站流程图网络营销简介
  • 网站链接网址怎么做百度推广一般多少钱
  • 甘肃做高端网站如何创建公司网站
  • 郑州网站制作汉狮网络现在网络推广哪家好
  • 网站建设试题2022千锋教育培训收费一览表
  • 企业做网站带来的好处企业查询免费
  • 个人链接怎么制作网站的seo 如何优化
  • 零售网站建设友情链接出售