安宁网站建设熊掌号,海南房地产网站,凡客诚品下载,眉山市住房和城乡建设部网站本专题再介绍几种经典的字串问题。 这是一个两个不重叠字串和的问题#xff0c;我们只要去枚举分界点c即可#xff0c;我们不妨让c作为右区间的左边界#xff0c;然后求[1,c)上的单个字串和并用max数组维护。对于右边#xff0c;我们只要反向求单个字串和然后选左边界为c的…本专题再介绍几种经典的字串问题。 这是一个两个不重叠字串和的问题我们只要去枚举分界点c即可我们不妨让c作为右区间的左边界然后求[1,c)上的单个字串和并用max数组维护。对于右边我们只要反向求单个字串和然后选左边界为c的一组即可。
下面是AC代码
#includestdio.h
#includecstdio
#includealgorithm
#includecstring
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 i1;in;i) scanf(%lld,ck[i]);for(int i1;in;i){if(i1){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 in;i1;i--){if(in) b[i]ck[i];else b[i]max(ck[i],ck[i]b[i1]);}hh-0x3f;for(int c2;cn;c){hhmax(hh,max1[c-1]b[c]);}printf(%lld\n,hh);}
}
接下来我们加点难度 现在2变成了m我们进行升维操作我们令f[i][j]为前j个数第j个数必须取组成的i个不相交子段最大和。
当我们要从j--j1时对于第j1,它可以作为最后一个子段的末尾也可以不做末尾而是起点而此时我们要去得到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就比如m1,有一种情况就是只选他自己因此要赋0
下面是AC代码dp数组用滚动即可
#includebits/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 i1;in;i) scanf(%d,a[i]);memset(dp,0,sizeof(dp));memset(ck,0,sizeof(ck));for(int i1;im;i){mmm-0x3f;for(int ji;jn;j){dp[j]max(dp[j-1],ck[j-1])a[j];ck[j-1]mmm;mmmmax(mmm,dp[j]);}}printf(%d\n,mmm); }
}
让我们再加点难度如果是环状呢 有一道石子合并的通过复制一份来解决但是因为这个不能利用上一次划分的情况换句话说这一次每次断开都要重新求原因在于不是区间dp)于是我们不妨想一想另一种方法
我们知道假如n与1没有被当成一段取跟上面的就一样了。
如果n与1被当成一段取那么我们在n与1断开的时候就相当于要求m1段区间其中第一段必须包含第一个元素最后一个必须包含最后一个元素。
下面是AC代码呜呜呜直接初值赋了-0x3f结果当成16进制检查了好久
#includebits/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 i1;in;i) scanf(%d,a[i]);for(int i1;in;i) dp1[i]a[i]dp1[i-1];for(int i1;in;i) ck1[i]max(dp1[i],ck1[i-1]);for(int in;i1;i--) hou[i]a[i]hou[i1];for(int in;i1;i--){if(in) maxx[i]a[i];else maxx[i]max(maxx[i1],hou[i]);}for(int i1;i2;i){mmm-10000000;for(int ji;jn;j){dp[j]max(dp[j-1],ck[j-1])a[j];ck[j-1]mmm;mmmmax(mmm,dp[j]);}}mmm1-10000000;for(int j2;jn;j){dp1[j]max(dp1[j-1],ck1[j-1])a[j];ck1[j-1]mmm1;mmm1max(mmm1,dp1[j]);}for(int i2;in-1;i){ansmax(ans,dp1[i]maxx[i1]);}printf(%d\n,max(mmm,ans)); }
接下来让我们再看看公共子序列问题吧 我们以前也写过我们把dp扩展成3维即可。
同时对于方案我们一般用last数组记录上一次的情况显然在这里就比较麻烦。我们可以用一个字符串每次3个的最后一个元素相等时记录一下即可。
