2016第七届蓝桥杯省赛-大学A组 密码脱落(区间dp)

2023-10-05 23:18

本文主要是介绍2016第七届蓝桥杯省赛-大学A组 密码脱落(区间dp),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

描述

X星球的考古学家发现了一批古代留下来的密码。 这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的镜像串)。 由于年代久远,其中许多种子脱落了,因而可能会失去镜像的特征。

你的任务是: 给定一个现在看到的密码串,计算一下从当初的状态,它要至少脱落多少个种子,才可能会变成现在的样子。

输入一行,表示现在看到的密码串(长度不大于1000) 要求输出一个正整数,表示至少脱落了多少个种子。

输入:

ABCBA

输出:

0

输入:

ABDCDCBABC

输出:

3

资源约定:

峰值内存消耗 < 256M CPU消耗 < 1000ms

请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。

所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。

注意: main函数需要返回0 注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。 注意:
所有依赖的函数必须明确地在源文件中 #include , 不能通过工程设置而省略常用头文件。

提交时,注意选择所期望的编译器类型。

思路

题目跟nyoj的还是回文差不多,用dp[i][j]表示代表从第i个字母到第j个字母使它成为回文串所要添加字母的个数

那么存在:dp[i][j]=min(dp[i+1][j]+1,dp[i][j-1]+1),当两个枚举的区间端点字母相等时,dp[i][j]=min(dp[i][j],dp[i+1][j-1])

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1000+10;
int dp[N][N];
string s;
int main()
{cin>>s;int len=s.length();for(int k=0; k<len; k++){for(int i=0; i+k<len; i++){int j=i+k;dp[i][j]=min(dp[i+1][j]+1,dp[i][j-1]+1);if(s[i]==s[j])dp[i][j]=min(dp[i][j],dp[i+1][j-1]);}}printf("%d\n",dp[0][len-1]);return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N=1000+10;
int dp[N][N];
string s;
int main()
{cin>>s;int len=s.length();for(int k=0; k<len; k++){for(int i=0; i+k<len; i++){int j=i+k;if(s[i]==s[j])dp[i][j]=dp[i+1][j-1];elsedp[i][j]=min(dp[i+1][j]+1,dp[i][j-1]+1);}}printf("%d\n",dp[0][len-1]);return 0;
}

这篇关于2016第七届蓝桥杯省赛-大学A组 密码脱落(区间dp)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring Security中用户名和密码的验证完整流程

《SpringSecurity中用户名和密码的验证完整流程》本文给大家介绍SpringSecurity中用户名和密码的验证完整流程,本文结合实例代码给大家介绍的非常详细,对大家的学习或工作具有一定... 首先创建了一个UsernamePasswordAuthenticationTChina编程oken对象,这是S

PostgreSQL数据库密码被遗忘时的操作步骤

《PostgreSQL数据库密码被遗忘时的操作步骤》密码遗忘是常见的用户问题,因此提供一种安全的遗忘密码找回机制是十分必要的,:本文主要介绍PostgreSQL数据库密码被遗忘时的操作步骤的相关资... 目录前言一、背景知识二、Windows环境下的解决步骤1. 找到PostgreSQL安装目录2. 修改p

Druid连接池实现自定义数据库密码加解密功能

《Druid连接池实现自定义数据库密码加解密功能》在现代应用开发中,数据安全是至关重要的,本文将介绍如何在​​Druid​​连接池中实现自定义的数据库密码加解密功能,有需要的小伙伴可以参考一下... 目录1. 环境准备2. 密码加密算法的选择3. 自定义 ​​DruidDataSource​​ 的密码解密3

SpringBoot如何对密码等敏感信息进行脱敏处理

《SpringBoot如何对密码等敏感信息进行脱敏处理》这篇文章主要为大家详细介绍了SpringBoot对密码等敏感信息进行脱敏处理的几个常用方法,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录​1. 配置文件敏感信息脱敏​​2. 日志脱敏​​3. API响应脱敏​​4. 其他注意事项​​总结

JavaScript实战:智能密码生成器开发指南

本文通过JavaScript实战开发智能密码生成器,详解如何运用crypto.getRandomValues实现加密级随机密码生成,包含多字符组合、安全强度可视化、易混淆字符排除等企业级功能。学习密码强度检测算法与信息熵计算原理,获取可直接嵌入项目的完整代码,提升Web应用的安全开发能力 目录

使用Java实现Navicat密码的加密与解密的代码解析

《使用Java实现Navicat密码的加密与解密的代码解析》:本文主要介绍使用Java实现Navicat密码的加密与解密,通过本文,我们了解了如何利用Java语言实现对Navicat保存的数据库密... 目录一、背景介绍二、环境准备三、代码解析四、核心代码展示五、总结在日常开发过程中,我们有时需要处理各种软

CentOS和Ubuntu系统使用shell脚本创建用户和设置密码

《CentOS和Ubuntu系统使用shell脚本创建用户和设置密码》在Linux系统中,你可以使用useradd命令来创建新用户,使用echo和chpasswd命令来设置密码,本文写了一个shell... 在linux系统中,你可以使用useradd命令来创建新用户,使用echo和chpasswd命令来设

Windows 上如果忘记了 MySQL 密码 重置密码的两种方法

《Windows上如果忘记了MySQL密码重置密码的两种方法》:本文主要介绍Windows上如果忘记了MySQL密码重置密码的两种方法,本文通过两种方法结合实例代码给大家介绍的非常详细,感... 目录方法 1:以跳过权限验证模式启动 mysql 并重置密码方法 2:使用 my.ini 文件的临时配置在 Wi

Python从零打造高安全密码管理器

《Python从零打造高安全密码管理器》在数字化时代,每人平均需要管理近百个账号密码,本文将带大家深入剖析一个基于Python的高安全性密码管理器实现方案,感兴趣的小伙伴可以参考一下... 目录一、前言:为什么我们需要专属密码管理器二、系统架构设计2.1 安全加密体系2.2 密码强度策略三、核心功能实现详解

SpringSecurity 认证、注销、权限控制功能(注销、记住密码、自定义登入页)

《SpringSecurity认证、注销、权限控制功能(注销、记住密码、自定义登入页)》SpringSecurity是一个强大的Java框架,用于保护应用程序的安全性,它提供了一套全面的安全解决方案... 目录简介认识Spring Security“认证”(Authentication)“授权” (Auth