XShell 方法 WorldCloud wxRuby Java Spring CPU javascript silverlight import gtk react视频教程 安卓项目实战 ps视频教程全集完整版 jq获取第一个子元素 jq延时 当前时间减一天 mysql新增用户和权限 yml文件注释 python编译环境 python中re模块 java新特性 java中instanceof jdk环境配置 java的集合 java多线程编程 java字符串操作 街头篮球辅助 内存修改器 subprocess 梦幻西游手游助手 adobe清理工具 微信小程序提示框 ipad锁屏 rar去广告 0x8002801c qq免安装版 中维高清监控系统安装 dnf传说 手机刷机助手 软件编程软件
当前位置: 首页 > 学习教程  > 编程语言

gym 102133 H(dp好题)

2021/1/13 20:45:53 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

gym 102133 H(dp好题) 挺难的dp,但是认真想还是可以写写的 题意: 给你两个字符串,要求这个字符串中部分不相交的长度至少为k的字符串能够组成ab两个字符串 思路: 首先我们可以转化一下,事实上就是将两个字符串分段…

gym 102133 H(dp好题)

挺难的dp,但是认真想还是可以写写的

题意:

给你两个字符串,要求这个字符串中部分不相交的长度至少为k的字符串能够组成ab两个字符串

思路:

首先我们可以转化一下,事实上就是将两个字符串分段拆开,段长度至少为k, 使得他们尽可能匹配,和LCS有点像?显然DP

原问题:

求两个字符串都匹配构造完的串的最小长度

子问题:

两个字符串前缀构造完的串的最小长度

事实上阶段隐性的是枚举构造的字符串的每一位往下一位转移,并且只有当前段匹配>=k,才能合法,所以状态是

d p [ i ] [ j ] [ k ] [ f ] dp[i][j][k][f] dp[i][j][k][f]表示a前i个,b的前j个,当前的a构造的部分串长度为k,b为f时候的最小串长。

边界 d p [ l e n 1 ] [ l e n 2 ] [ 0 ] [ 0 ] dp[len1][len2][0][0] dp[len1][len2][0][0],此处我们用部分串为0的时候标记当前匹配完成。

所以转移就下面几种:

两字符相等,继续匹配

当前a处于结束的状态,保持结束。b继续,b处于结束保持,a继续,应该不难理解,因为我截取某段出来的时候,可能放后面让他和a匹配会更多

最最重要的是,当某段>=k的时候,就可以为当前段结束统计答案了,这里我是用0强行标记的

这题空间不够,要压维

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
const int INF=0x3f3f3f3f; 
int dp[2][maxn][maxn][maxn],limit=0;//前i,j,当前k,l
char s1[maxn],s2[maxn],len1,len2;
int solve(){ 
    for(int i=0;i<=len2;++i)
        for(int j=0;j<=len1;++j)
            for(int k=0;k<=len2;++k)
                dp[0][i][j][k]=INF;
    dp[0][0][0][0]=0;
    for(int i=0;i<=len1;++i){ 
        for(int j=0;j<=len2;++j)
            for(int k=0;k<=len1;++k)
                for(int f=0;f<=len2;++f){ 
                    dp[(i+1)&1][j][k][f]=INF;
                }
        for(int j=0;j<=len2;++j){ 
            for(int k=len1;k>=0;--k)
                for(int f=len2;f>=0;--f){ 
                    if(dp[i&1][j][k][f]==INF)continue;
                    if(k>=limit&&f>=limit)dp[i&1][j][0][0]=min(dp[i&1][j][0][0],dp[i&1][j][k][f]);
                    if(k>=limit)dp[i&1][j][0][f]=min(dp[i&1][j][0][f],dp[i&1][j][k][f]);               //当前段是否匹配完成
                    if(f>=limit)dp[i&1][j][k][0]=min(dp[i&1][j][k][0],dp[i&1][j][k][f]);
                    
                    if(i!=len1&&!f)
                        dp[(i+1)&1][j][k+1][0]=min(dp[(i+1)&1][j][k+1][0],dp[i&1][j][k][f]+1);//s1匹配 s2等下个位置
                    if(j!=len2&&!k)
                        dp[i&1][j+1][0][f+1]=min(dp[i&1][j+1][0][f+1],dp[i&1][j][k][f]+1);//s1等下个位置
                    if(i!=len1&&j!=len2){ 
                        if(s1[i+1]==s2[j+1])
                            dp[(i+1)&1][j+1][k+1][f+1]=min(dp[(i+1)&1][j+1][k+1][f+1],dp[i&1][j][k][f]+1);//都匹配一步
                }
            }
        }
    }
    return dp[(len1)&1][len2][0][0];
}
int main(){ 
    scanf("%d%s%s",&limit,s1+1,s2+1);
    len1=strlen(s1+1),len2=strlen(s2+1);
    cout<<solve();
    return 0;

}


本文链接: http://www.dtmao.cc/news_show_600443.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?