Pieces
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 311 Accepted Submission(s): 172
Problem Description
You heart broke into pieces.My string broke into pieces.But you will recover one day,and my string will never go back.
Given a string s.We can erase a subsequence of it if this subsequence is palindrome in one step. We should take as few steps as possible to erase the whole sequence.How many steps do we need?
For example, we can erase abcba from axbyczbea and get xyze in one step.
Given a string s.We can erase a subsequence of it if this subsequence is palindrome in one step. We should take as few steps as possible to erase the whole sequence.How many steps do we need?
For example, we can erase abcba from axbyczbea and get xyze in one step.
Input
The first line contains integer T,denote the number of the test cases. Then T lines follows,each line contains the string s (1<= length of s <= 16).
T<=10.
T<=10.
Output
For each test cases,print the answer in a line.
Sample Input
2
aa
abb
Sample Output
1
2
Source
Recommend
zhuyuanchen520
题意:
给定一个串,每次可以删除一个回文子串,问把全串删干净的最少次数。
思路:
用状态压缩把所有的状态枚举出来,用数组记录所表示状态所有字符被删除干净的最少次数。
状态:dp[x]表示在状态x下把所有字符删除的最少次数。
状态压缩:dp[x] = min{dp[x], dp[k]}(k是x的子集)
这样的dp的边界不再是dp[0]或dp[n]了。而是对每个状态都要设定原始值,如果某个状态是完全回文的,则dp[x] = 1,否则,dp[x] 就是一个最大值(目前子串的长度)
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int N=16; const int INF=0x3f3f3f3f; char str[30]; int len,dp[1<<16]; vector<int> vt; int solve(int k){ vt.clear(); for(int i=0;i<=len;i++) if(k&(1<<i)) vt.push_back(i); int sz=vt.size()-1; for(int i=0;i<sz/2;i++) if(str[vt[i]]!=str[vt[sz-i]]) return vt.size(); return 1; } int main(){ //freopen("input.txt","r",stdin); int t; scanf("%d",&t); while(t--){ scanf("%s",str); len=strlen(str); for(int i=1;i<=(1<<len)-1;i++){ dp[i]=solve(i); for(int j=i;j;j=(j-1)&i) dp[i]=min(dp[i],dp[j]+dp[j^i]); } printf("%d\n",dp[(1<<len)-1]); } return 0; }
相关推荐
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
DP(Dynamic Programming,动态规划)是一种非常重要的算法思想,在 ACM HDU 题目分类中,DP 问题占据了很大的比例。例如,1003 DP 经典问题,最大连续子段和;1024 经典 DP,最大 M 子段和;1025 经典 DP,最长递增...
标题中的“DP.rar”表明这是一个关于动态规划的资料压缩包,而“DP_hdu”暗示了这些题目可能来自杭州电子科技大学(HDU)的在线编程平台。动态规划通常用于解决那些可以通过子问题的最优解来构建原问题最优解的问题...
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
hdu 1005.比较简单的一道题,有兴趣的可以看看。
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
在HDU OJ中,DP题目如1003、1024等,通常需要选手对状态进行定义,并找出状态转移方程,从而求得问题的最优解。这类题目考验的是选手对复杂问题的抽象能力和优化策略的运用。 ### 搜索 搜索算法是解决问题的一种...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
题目名为“hdu 1257 最低拦截系统”,这里的“最低拦截系统”实际上是描述了一个问题场景,而具体的问题通过描述部分可以得知是要求找出给定数组中的最长递增子序列的长度。这里所谓的“最低拦截系统”可能是为了...
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...
* 题目1044:Collect More Jewels,涉及到动态规划(DP)的概念。 3. 图的搜索:图的搜索算法、图的路径查找等。 * 题目1067:Gap,涉及到图的搜索算法。 * 题目1072:Nightmare,涉及到完全搜索的概念。 4. 图的...
hdu2101AC代码
【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...