题目链接
区间 DP 的经典模型之一。
题意是将整个串通过四种操作变成一个回文串,根据套路,不难设计出 dp[i][j] 表示为使区间 [i, j] 成为回文串的最少操作次数。
先判断 a[i] 是否等于 a[j],如果相等,那么:
f[i][j] = max(f[i][j], f[i + 1][j - 1])
如果不相等,则改变一个:
f[i][j] = max(f[i][j], f[i + 1][j - 1] + 1)
其实可以发现第一、二种操作都和第三种等价,这三种转移可以表示为:
f[i][j] = max(f[i][j - 1], f[i + 1][j]) + 1
对于区间 DP,已经得到答案的区间我们都可以直接认为它是已满足题意要求的性质的,因为所记录的答案就是使其成立的最小代价。
然后设计方程乱搞,对于该模型就是考虑让区间两端点满足性质的问题……
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int maxn = + ;
int n, a[maxn], dp[maxn][maxn]; int main(int argc, char const *argv[])
{
freopen("nanjolno.in", "r", stdin);
freopen("nanjolno.out", "w", stdout); scanf("%d", &n);
for(int i = ; i <= n; ++i) scanf("%d", &a[i]);
for(int i = ; i <= n; ++i) {
for(int l = ; l + i - <= n; ++l) {
int r = l + i - ;
if( a[l] == a[r] ) dp[l][r] = dp[l + ][r - ];
else dp[l][r] = min(dp[l + ][r - ], min(dp[l][r - ], dp[l + ][r])) + ;
}
}
printf("%d\n", dp[][n]); fclose(stdin), fclose(stdout);
return ;
}
—— 与漫长的人生相比,两人共处的时间仅一瞬间;
[TJOI2007] 调整队形的更多相关文章
-
洛谷P3847 [TJOI2007]调整队形
P3847 [TJOI2007]调整队形 题目背景 学校艺术节上,规定合唱队要参加比赛,各个队员的衣服颜色不能很混乱:合唱队员应排成一横排,且衣服颜色必须是左右对称的. 例如:“红蓝绿蓝红”或“红蓝绿 ...
-
【Luogu】P3847调整队形(DP)
题目链接 DP果真是考思维啊 增加一个数的操作等价于删掉那个不和谐的数的操作. 所以1.2操作可以忽略. 剩下3.4操作,则可以设计f[i][j]是将区间[i,j]变成回文序列需要的操作数. if(a ...
-
经典DP模型--回文词--IOI2000
[问题描述]回文词是一种对称的字符串--也就是说, 一个回文词, 从左到右读和从右到左读得到的结果是一样的. 任意给定一个字符串, 通过插入若干字符, 都可以变成一个回文词. 你的任务是写一个程序, ...
-
伪造队形(FFT)
题目描述Tukkun带着他的合唱队去环形音乐厅参加演出.上场前,Tukkun发现了严重的问题:音乐厅的工作人员把他们的合唱队形搞错了.具体来说,Tukkun的合唱队有N个人围成一圈,身高按照顺时针顺序 ...
-
.Net Core MVC 网站开发(Ninesky) 2.3、项目架构调整(续)-使用配置文件动态注入
上次实现了依赖注入,但是web项目必须要引用业务逻辑层和数据存储层的实现,项目解耦并不完全:另一方面,要同时注入业务逻辑层和数据访问层,注入的服务直接写在Startup中显得非常臃肿.理想的方式是,w ...
-
.Net Core MVC 网站开发(Ninesky) 2.3、项目架构调整-控制反转和依赖注入的使用
再次调整项目架构是因为和群友dezhou的一次聊天,我原来的想法是项目尽量做简单点别搞太复杂了,仅使用了DbContext的注入,其他的也没有写接口耦合度很高.和dezhou聊过之后我仔细考虑了一下, ...
-
C#中如何调整图像大小
在本篇文章中,我将介绍如何在C#中来调整你想要的图像大小.要实现这一目标,我们可以采取以下几个步骤: 1.首先要获取你想要调整大小的图像: string path = Server.MapPath(& ...
-
BPM配置故事之案例9-根据表单数据调整审批线路2
老李:好久不见啊,小明. 小明:-- 老李:不少部门有物资着急使用,现在的审批流程太慢了,申请时增加一个是否加急的选项吧.如果选加急,金额1000以下的直接到我这里,我审批完就通过,超过1000的直接 ...
-
如何实现可动态调整隐藏header的listview
(转自:http://blog.sina.com.cn/s/blog_70b9730f01014sgm.html) 需求:根据某种需要,可能需要动态调整listview的页眉页脚,譬如将header作 ...
随机推荐
-
Python之Django【进阶篇 】
Model 到目前为止,当我们的程序涉及到数据库相关操作时,我们一般都会这么搞: 创建数据库,设计表结构和字段 使用 MySQLdb 来连接数据库,并编写数据访问层代码 业务逻辑层去调用数据访问层执行 ...
-
【Hadoop】Hive HSQ 使用 &;&; 自定义HQL函数
4 HQL 4.1 官网 4.1.1 https://cwiki.apache.org/confluence/display/Hive/LanguageManual 4.1.2 性能调优 4.1.2. ...
-
ecshop显示所有分类树栏目
1.找到 category.php 和goods.php 两个文件修改: $smarty->assign('categories', get_categories_tree(0)); // 分类 ...
-
如何成为一名优秀的C程序员
如何成为一名优秀的C程序员 英文原文:To become a good C programmer 问题的提出 每过一段时间我总会收到一些程序员发来的电子邮件,他们会问我是用什么编程语言来编写自己的游戏 ...
-
The algorithm learning of sort which include Bubblesort,Insertsort,Quicksort and Mergesort.
Notice : these algorithms achieved by Java. So,let's going to it. firstly, what is Bubblesort? why w ...
-
SpringMVC用到的jar包
SpringMVC用到的jar包 自己搭建一个SpringMVC框架时需要用到相应的jar包,参考下载网址: http://repo.spring.io/release/org/springframe ...
-
网站 HTTP 升级 HTTPS 完全配置手册
网站 HTTP 升级 HTTPS 完全配置手册 今天,所有使用Google Chrome稳定版的用户迎来了v68正式版首个版本的发布,详细版本号为v68.0.3440.75,上一个正式版v67.0.3 ...
-
新安装的win7/win10系统,所有驱动都没安装,插入U盘也无法识别解决方法
我是使用老毛挑安装的系统,结果安装好之后,才发现所有驱动都没有安装,例如usb,网卡驱动等 解决方法就是先把驱动下载到系统安装盘里面,然后再次进入安装系统界面,相当于重新安装系统,但实际上我们不需要. ...
-
Codeforces 595D - Max and Bike
595D - Max and Bike 思路:开始和结束时的计时器的高度相同时(也就是关于圆竖着直径对称)时间最少. 证明: 总距离为d. 圆周长为s=2*π*r. 设len=d-floor(d/s) ...
-
[leetcode sort]147. Insertion Sort List
Sort a linked list using insertion sort. 利用插入排序对一个链表进行排序 思路和数组中的插入排序一样,不过每次都要从链表头部找一个合适的位置,而不是像数组一样可 ...