【UVA】10739 - String to Palindrome(动态规划)

2024-09-07 23:48

本文主要是介绍【UVA】10739 - String to Palindrome(动态规划),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

比较水的动态规划

dp[i][j] 将原串 i ~ j 之内的字符转化为回文字符所需要的最小操作次数

其中删除操作和添加操作本质上是一样的。

三个状态转移方程:

dp[i][j] = min(dp[i][j] ,dp[i + 1][j]);

dp[i][j] = min(dp[i][j] ,dp[i + 1][j - 1]);

dp[i][j] = min(dp[i][j] ,dp[i][j - 1]);

如果 i = j  dp[i][j] = 0;

14145138 10651 Pebble Solitaire Accepted C++ 0.009 2014-09-04 09:09:42

#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
#include<iostream>
using namespace std;
#define MAXD 1000 + 10
#define INF 10000
char str[MAXD];
int dp[MAXD][MAXD];
int dfs(int start,int last){if(dp[start][last] != -1)return dp[start][last];if(start == last)return dp[start][last] = 0;if(str[start] == str[last]){if(start + 1 == last)return dp[start][last] = 0;elsereturn dp[start][last] = dfs(start + 1 , last - 1);}dp[start][last] = INF;if(last - 1 >= start)dp[start][last] = min(dp[start][last],dfs(start,last - 1) + 1);if(start + 1 <= last)dp[start][last] = min(dp[start][last],dfs(start + 1, last) + 1);if(start + 1 <= last - 1)dp[start][last] = min(dp[start][last],dfs(start + 1,last - 1) + 1);return dp[start][last];
}
int main(){int T;scanf("%d",&T);for(int Case = 1; Case <= T; Case ++){scanf("%s",str);memset(dp,-1,sizeof(dp));int ans = dfs(0,strlen(str) - 1);printf("Case %d: %d\n",Case,ans);}return 0;
}

这篇关于【UVA】10739 - String to Palindrome(动态规划)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1146510

相关文章

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

java String.join()方法实例详解

《javaString.join()方法实例详解》String.join()是Java提供的一个实用方法,用于将多个字符串按照指定的分隔符连接成一个字符串,这一方法是Java8中引入的,极大地简化了... 目录bVARxMJava String.join() 方法详解1. 方法定义2. 基本用法2.1 拼接

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题(Topic)的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht

golang实现动态路由的项目实践

《golang实现动态路由的项目实践》本文主要介绍了golang实现动态路由项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习... 目录一、动态路由1.结构体(数据库的定义)2.预加载preload3.添加关联的方法一、动态路由1

Python Selenium动态渲染页面和抓取的使用指南

《PythonSelenium动态渲染页面和抓取的使用指南》在Web数据采集领域,动态渲染页面已成为现代网站的主流形式,本文将从技术原理,环境配置,核心功能系统讲解Selenium在Python动态... 目录一、Selenium技术架构解析二、环境搭建与基础配置1. 组件安装2. 驱动配置3. 基础操作模

慢sql提前分析预警和动态sql替换-Mybatis-SQL

《慢sql提前分析预警和动态sql替换-Mybatis-SQL》为防止慢SQL问题而开发的MyBatis组件,该组件能够在开发、测试阶段自动分析SQL语句,并在出现慢SQL问题时通过Ducc配置实现动... 目录背景解决思路开源方案调研设计方案详细设计使用方法1、引入依赖jar包2、配置组件XML3、核心配

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》:本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务,增加、删

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾