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。

相关文章

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
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
hdu4865(概率DP)

hdu4865(概率DP)

题意：已知前一天和今天的天气概率，某天的天气概率和叶子的潮湿程度的概率，n天叶子的湿度，求n天最有可能的天气情况。 思路：概率DP，dp[i][j]表示第i天天气为j的概率，状态转移如下：dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下： #include <stdio.h>#include
阅读更多...
csu1328（近似回文串）

csu1328（近似回文串）

题意：求近似回文串的最大长度，串长度为1000。 解题思路：以某点为中心，向左右两边扩展，注意奇偶分开讨论，暴力解即可。时间复杂度O(n^2); 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu
阅读更多...
usaco 1.1 Broken Necklace（DP）

usaco 1.1 Broken Necklace（DP）

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于： 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2