NYOJ37、1023、15(回文串、括号匹配、记忆化搜索、dp，区间dp)

2024-04-05 23:38
文章标签 dp 15 搜索 括号 匹配 回文 记忆 区间 1023 nyoj37

本文主要是介绍NYOJ37、1023、15(回文串、括号匹配、记忆化搜索、dp，区间dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

回文字符串

时间限制：3000 ms  |  内存限制：65535 KB

难度：4

输入

第一行给出整数N（0<N<100）
接下来的N行，每行一个字符串，每个字符串长度不超过1000.

输出

每行输出所需添加的最少字符数

样例输入

1
Ab3bd

样例输出

2

描述

所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如"aba"。当然，我们给你的问题不会再简单到判断一个字符串是不是回文字符串。现在要求你，给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成为回文字符串。

这题是2000IOI题。

想了半天，终于AC了，开心~~~。

定义状态 dp[i][j] 表示 区间 i-j 内最少添加的字符个数。

则容易得到状态转移方程

dp[i][j] =\left\{\begin{matrix} min(dp[i+1][j],dp[i][j-1]) + 1 \\ dp[i+1][j-1] \qquad s.t\;(a[i] == a[j]) \end{matrix}\right.

即当 a[i] == a[j]  时候，不增加计数，否则增加计数

 

code（记忆化搜索）：

 

#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int N = 1000+5;
int dp[N][N];
char a[N];int rec(int i, int j){if(i >= j)return dp[i][j] = 0;if(dp[i][j] != -1)return dp[i][j];int & ans = dp[i][j];if(a[i] == a[j])ans = rec(i+1,j-1);elseans = min(rec(i+1,j),rec(i,j-1)) + 1;return ans;
}int main(){int t;scanf("%d",&t);while(t--){memset(dp,-1,sizeof(dp));scanf("%s",a);int ans = rec(0,strlen(a)-1);printf("%d\n",ans);}return 0;}

看了其他代码，似乎还有种方法，是求反转串与原串最长公共子序列，答案就是原串的长度减去最长公共子串的长度。

和我的思路不大一样。

 

这题可以用另一种方法，就是把原字符串取反，然后和原串求最长公共子串，然后用总长度减去最长公共子串长度，得到的即为结果。

可以理解最长公共子串为不添加字符即满足条件的字符，其它的需要在对称位置添加字符。

code2(最长公共子串)：

#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int N = 1005;
char s1[N],s2[N];
int dp[N][N];int main(){int t,len;scanf("%d",&t);while(t--){memset(dp,0,sizeof(dp));scanf("%s",&s1[1]);len = strlen(&s1[1]);for(int i = len; i > 0; --i){s2[i] = s1[len-i+1];}for(int i = 1; i <= len; ++i){for(int j = 1; j <= len; ++j){if(s1[i] == s2[j]){dp[i][j] = dp[i-1][j-1] + 1;}else{dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}}}printf("%d\n",len-dp[len][len]);}return 0;}

 

区间dp思想

尝试写的递推（超时了）：

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<string>
using namespace std;const int N = 1000+5;
int dp[N][N];
const int INF = 1 << 30;
char a[N];int main(){int t;scanf("%d",&t);int len;while(t--){memset(dp,INF,sizeof(dp));scanf("%s",a);len = strlen(a);for(int i = 0; i < len; ++i){for(int j = 0; j < len; ++j){if(i >= j)dp[i][j] = 0;}}bool flag = true;for(int i = 0; i < len; ++i){if(a[i] != a[len-i-1])flag = false;}if(flag){printf("%d\n",0);continue;}for(int l = 2; l <= len; ++l){for(int i = 0; i + l <= len; ++i){int j = i+l-1;for(int k = i; k < j; ++k){if(a[i] == a[j]){dp[i][j] = dp[i+1][j-1];}elsedp[i][j] = min(dp[i+1][j],dp[i][j-1]) + 1;}}}printf("%d\n",dp[0][len-1]);}return 0;}

还是回文

时间限制：2000 ms  |  内存限制：65535 KB

难度：3

输入

多组数据
第一个有两个数n,m，分别表示字符的种数和字符串的长度
第二行给出一串字符，接下来n行，每行有一个字符(a~z)和两个整数，分别表示添加和删除这个字符的花费
所有数都不超过2000

输出

最小花费

样例输入

3 4
abcb
a 1000 1100
b 350 700
c 200 800

样例输出

900

描述

判断回文串很简单，把字符串变成回文串也不难。现在我们增加点难度，给出一串字符(全部是小写字母)，添加或删除一个字符，都会产生一定的花费。那么，将字符串变成回文串的最小花费是多少呢？

 

这题为什么这句不被放在 else里，而是总是执行？

dp[i][j] = min(dp[i+1][j]+cost[s[i]],dp[i][j-1]+cost[s[j]]) \\式1

原因：

例如 求 abaa  可以转化为 求aba （去除右边的a） 和 ba (去除两侧的a因为他们想等，可以去除)

但是如果 如果 式1 被放在else里面了， 就不同时考虑上面 aba 与ba 这两情况了，前者操作花费为 a, 后者花费为右侧侧添加b

这显然是不同的花费，但是如果添加了else，这就只会单独被考虑一种(取决于 语句顺序)。

其实可以理解为，总是要考虑着两种情况的，只是有一种情况考虑之前需要满足a[i] == a[j]  所以才加上的if语句。

并不是为了把两种情况单独分开考虑。

code1：

注意dp必须要初始化为0  ，这是为了服务于 i >= j 时候 结果为 0 设计的

#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int N = 2000 + 5;
char s[N];
int cost[200];
int dp[N][N];
int main(){int n,m,x,y;char ss[2];while(scanf("%d%d",&n,&m) != EOF){scanf("%s",s);for(int i = 1; i <= n; ++i){scanf("%s%d%d",ss,&x,&y);cost[ss[0]] = min(x,y);}memset(dp,0,sizeof(dp));for(int l = 2; l <= m; ++l){for(int i = 0; i < m-l+1; ++i){int j = i+l-1;dp[i][j] = min(dp[i+1][j]+cost[s[i]],dp[i][j-1]+cost[s[j]]);if(s[i] == s[j])dp[i][j] = min(dp[i+1][j-1],dp[i][j]);}}printf("%d\n",dp[0][m-1]);}return 0;}

另一种递推式写法：

两种遍历的次序不同，但是异曲同工

           memset(dp,0,sizeof(dp));for(int j = 1; j < m; ++j){for(int i = j-1; i >= 0; --i){dp[i][j] = min(dp[i+1][j]+cost[s[i]],dp[i][j-1]+cost[s[j]]);if(s[i] == s[j])dp[i][j] = min(dp[i+1][j-1],dp[i][j]);}}

 

另外、这题用记忆化搜索超时了（可能是频繁的memset(dp) 超时？）

code(超时)：

#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int N = 200;
//int del[N],add[N];
int cost[N];
char ts[2];
int dp[2000+5][2000+5];
char s[2000+5];
const int INF = 1 << 30;int rec(int i, int j){if(i >= j)return 0;if(dp[i][j] >= 0)return dp[i][j];int & ans = dp[i][j];ans = min(rec(i+1,j)+cost[s[i]],rec(i,j-1)+cost[s[j]]);if(s[i] == s[j])ans = rec(i+1,j-1);//ans = min(min(rec(i+1,j)+add[s[i]],rec(i+1,j)+del[s[i]]),min(rec(i,j-1)+add[s[j]],rec(i,j-1)+del[s[j]]));return ans;
}int main(){int n,m;char c;int x,y;while(~scanf("%d%d",&n,&m)){memset(dp,-1,sizeof(dp));getchar();scanf("%s",&s);for(int i = 0; i < n; ++i){getchar();scanf("%s%d%d",&ts,&x,&y);cost[ts[0]] = min(x,y);}printf("%d\n",rec(0,m-1));}return 0;}

题三（括号匹配）

code1（记忆化搜索）

#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int N = 100+5;
int dp[N][N];
bool vis[N][N];
char s[100+5];int rec(int i,int j){if(i > j)return 0;if(i == j)return 1; // 说明 没有匹配if(vis[i][j])return dp[i][j];int & ans = dp[i][j];if(s[i] == '(' && s[j] == ')' || s[i] == '[' && s[j] == ']')ans = min(ans,rec(i+1,j-1));if(s[i] == '(' || s[i] == '[')ans = min(ans,rec(i+1,j)+1);if(s[j] == ')' || s[j] == ']')ans = min(ans,rec(i,j-1)+1);for(int k = i; k < j; ++k){ans = min(ans,rec(i,k)+rec(k+1,j));}vis[i][j] = true; //求出dp[i][j] 后标记 为 truereturn ans;
}int main(){int t;scanf("%d",&t);while(t--){memset(vis,false,sizeof(vis));memset(dp,0x3f,sizeof(dp)); //初始化为无穷大scanf("%s",s);printf("%d\n",rec(0,strlen(s)-1));}return 0;}

注意两者的 dp 初始化方式不同、但本质一样、这里面也是一样 if语句之间不能加else、每种情况都需要考虑。

code2(递推):

#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 100+5;
int dp[N][N];
char s[N];int main(){int t,len;scanf("%d",&t);while(t--){memset(dp,0,sizeof(dp));scanf("%s",s);len = strlen(s);for(int i = 0; i < len; ++i){for(int j = 0; j < len; ++j){if(i == j)dp[i][j] = 1;else if(i > j)dp[i][j] = 0;elsedp[i][j] = INF;}}for(int l = 1; l <= len; ++l){for(int i = 0; i < len-l+1; ++i){int j = i+l-1;if(s[i] == '(' && s[j] == ')' || s[i] == '[' && s[j] == ']')dp[i][j] = min(dp[i+1][j-1],dp[i][j]);if(s[i] == '(' || s[i] == '[')dp[i][j] = min(dp[i+1][j]+1,dp[i][j]);if(s[j] == ')' || s[j] == ']')dp[i][j] = min(dp[i][j],dp[i][j-1]+1);for(int k = i; k < j; ++k){dp[i][j] = min(dp[i][k]+dp[k+1][j],dp[i][j]);//切分的情况}}}printf("%d\n",dp[0][len-1]);}return 0;}

 

这篇关于NYOJ37、1023、15(回文串、括号匹配、记忆化搜索、dp，区间dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/878458。

相关文章

C++使用栈实现括号匹配的代码详解

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中，括号匹配是一个常见问题，尤其是在
阅读更多...
关于Gateway路由匹配规则解读

关于Gateway路由匹配规则解读

《关于Gateway路由匹配规则解读》本文详细介绍了SpringCloudGateway的路由匹配规则,包括基本概念、常用属性、实际应用以及注意事项,路由匹配规则决定了请求如何被转发到目标服务,是Ga... 目录Gateway路由匹配规则一、基本概念二、常用属性三、实际应用四、注意事项总结Gateway路由
阅读更多...
Springboot的ThreadPoolTaskScheduler线程池轻松搞定15分钟不操作自动取消订单

Springboot的ThreadPoolTaskScheduler线程池轻松搞定15分钟不操作自动取消订单

《Springboot的ThreadPoolTaskScheduler线程池轻松搞定15分钟不操作自动取消订单》：本文主要介绍Springboot的ThreadPoolTaskScheduler线... 目录ThreadPoolTaskScheduler线程池实现15分钟不操作自动取消订单概要1，创建订单后
阅读更多...
C# ComboBox下拉框实现搜索方式

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这
阅读更多...
Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
这15个Vue指令，让你的项目开发爽到爆

这15个Vue指令，让你的项目开发爽到爆

1. V-Hotkey 仓库地址: github.com/Dafrok/v-ho… Demo: 戳这里 https://dafrok.github.io/v-hotkey 安装: npm install --save v-hotkey 这个指令可以给组件绑定一个或多个快捷键。你想要通过按下 Escape 键后隐藏某个组件，按住 Control 和回车键再显示它吗？小菜一碟： <template
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
hdu4826（三维DP）

hdu4826（三维DP）

这是一个百度之星的资格赛第四题 题目链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意：从左上角的点到右上角的点，每个点只能走一遍，走的方向有三个：向上，向下，向右，求最大值。 咋一看像搜索题，先暴搜，TLE,然后剪枝，还是TLE.然后我就改方法，用DP来做，这题和普通dp相比，多个个向上
阅读更多...
hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2