bzoj1068(区间dp,字符串压缩)

By | 08月17日
Advertisement

这类题真心不会,想思路直接呵呵。。

f[l][r][k]表示i-j这段区间,是否放置M(k=1/0)压缩到的最短长度。我们标记此时l-1一定是有M的,或者l-1=0。就是,在这段区间l~r放R的话,一定是从l开头到R的位置和R后面的位置相同,其实就是保证了,l到R之间没有M

对于k=1,及对于在这个区间放m,我们分四种情况:

首先枚举M的位置i,然后对于被M分割的两个区间l到i,i+1到r:在两个区间中间放M,因为要保证每个区间l-1是M,再能保证性质

k可以是

1,1

1,0

0,1

0,0

对于k=0,分两种情况:

如果此时左右两半相同,那么右边可以用R代替;

递归处理左边最多能压缩到什么,注意此时递归t要等于0,因为左部分不能放M

另外,有一些是不被压缩的,枚举循环结束的位置i,i+1到r不做处理。

答案就是min(f[1][l][1],f[1][l][0])

为什么这就是对的,为什么这么想?(这题要好好记录一下)

首先,对于一个区间来说,我们要把它压缩,有哪些方案,决策?

最简单的,如果这个区间左右两半是相同的,就直接把它压缩就好。//第三种操作

另一种情况,还是这个l~r的区间,如果左边的l~k是左右两边对称的,后边的就不构成对称了,那么两种情况

右边也能自成一个对称--》中间加一个M,处理右边//第一种操作

右边不能成对称了--》直接把右边的长度加上//第二中操作

这只是一些情况,还有很多,通用来说的话:

就是1:压缩前面和后面

2:只压缩前面

3:整个压缩

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;

int f[60][60][2];
int n;
char s[60];
bool same(int l,int r)
{
	int len=(r-l+1);
	if (len&1) return false;
	len>>=1;
	int tmp=l+len;
	for (int i=1;i<=len;i++) if (s[i+l-1]!=s[i+tmp-1]) return false;
	return true;
}
int dfs(int l,int r,int t)
{
	if (l==r) return 1;
	if (f[l][r][t]!=-1) return f[l][r][t];

	int ans=r-l+1;
	if (t==1)
	for (int i=l;i<r;i++)
ans=min(ans,1+min(dfs(l,i,0),dfs(l,i,1))+min(dfs(i+1,r,0),dfs(i+1,r,1)));

	for (int i=l;i<r;i++) ans=min(ans,dfs(l,i,t)+r-i);

	if (t==0&&same(l,r))
	{
		int mid=(l+r)>>1;
		ans=min(ans,dfs(l,mid,0)+1);
	}
	f[l][r][t]=ans;
	return ans;
}

int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);

	memset(f,-1,sizeof(f));
	printf("%d",min(dfs(1,n,0),dfs(1,n,1)));

	return 0;
}

Similar Posts:

  • UVa11584Partitioning by Palindromes(字符串区间dp)

    UVa11584Partitioning by Palindromes(字符串区间dp) 题意:给定一个字符串s, 问说最少可以划分成几个回文串. 思路:dp[i]表示从1到第i个字符最少可以划分为几个回文,状态转移方程 dp[i] = min(dp[i], dp[j-1]+1), 如果满足 s[j] 到 s[i] 为回文字符串. 用 judge 函数判断从j到i是否可以形成回文串. Sample Input 3 racecar fastcar aaadbccb Sample Output 1

  • POJ 1159 Palindrome(区间DP/最长公共子序列+滚动数组)

    Palindrome Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 56150 Accepted: 19398 Description A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a prog

  • ZOJ 1463 POJ 1141 Brackets Sequence (区间DP) #by Plato

    ZOJ 1463 POJ1141 Brackets Sequence (区间DP) #by Plato http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=463 题意: 给一个括号序列,求 为使序列合法化所需要添加的最少括号书.要求输出合法化后的序列. Idea: 比较明显的DP了, f[i][j] 代表从 第i个元素到第j个元素所需要添加的最小括号数, 以i-j的距离扩大开始DP, 4种状态转移的方式: 条件 结果 路径 a[

  • code vs 1029 遍历问题 区间dp

    http://codevs.cn/problem/1029/ 给出一棵二叉树(节点是小写字符)的按照先序遍历和后续遍历得到的字符串,其实就是求有多少和二叉树的先序遍历和后序遍历满足这两个字符串. 区间dp:dp(l, r, a, b)表示s字符串的(l, r)段和t字符串的(a, b)段相匹配的方案数.那么s[l]和t[b]必须一样,因为这两个是这一段的根节点.然后我们再枚举(l,r)的左子树(l+1,k)和(a,b)的左子树(a,a+k-l-1); dp(l,r,a,b) = sum(dp(l

  • 区间dp小结

    区间dp,顾名思义,就是在区间上dp,即把整个区间划分为一个个的小区间,在小区间内dp求出最优值,然后把这些小区间合并以后就是整个取件的最优值. 下面是一些比较经典的区间dp题目: 1.NYOJ 737 石子合并:http://acm.nyist.net/JudgeOnline/problem.php?pid=737 题意:有n堆石子,每堆有a[i]个,每次合并时只能合并相邻的两堆,代价为两堆石子的个数之和.问把这n堆石子合并成一堆需要的最小代价是多少. 状态:dp[i][j] 表示合并第 i

  • HDU 2476 String painter(区间DP啊)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2476 Problem Description There are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a powerful string painter. With the help of the painter, you can cha

  • LA 3516 区间dp

    #include <cstdio> #include <cstring> using namespace std; const int maxn = 300 + 10; const int MOD = 1E9; typedef long long LL; char S[maxn]; int d[maxn][maxn]; int dp(int i, int j) { if (i == j) return 1; if (S[i] != S[j]) return 0; int &

  • HDU3280:Cheapest Palindrome(区间DP)

    Description Keeping track of all the cows can be a tricky task so Farmer John has installed a system to automate it. He has installed on each cow an electronic ID tag that the system will read as the cows pass by a scanner. Each ID tag's contents are

  • hdu 4632 Palindrome subsequence (区间DP+容斥)

    Problem Description In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence < A, B, D> is a subsequence of < A

  • Vijos 1100 (区间DP)

    题目链接: https://vijos.org/p/1100 题目大意:NOIP著名的加分二叉树.给出一棵树的中序遍历,加分规则左子树*右子树+根.空子树分数为1.问最大加分的树结构,输出树结构的先序遍历. 解题思路: 先从小的问题看起. 对于一棵子树,只要知道根是啥,就能轻松求出这棵子树的加分情况. 那么就变成枚举根的区间DP问题. 由于要输出先序遍历,则用m[i][j]记录在i~j区间选择的根. 区间DP边界: ①一个点情况:即无左右子树,dp[i][i]=node[i],m[i][i]=i

  • nyoj746整数划分(四)【区间dp】

    区间dp的第一道题,各种sb错误== 1.中间输出和必要的步骤要分开写,要不就容易把重要的部分注释掉 2.提交前自己写示例! /****************** nyoj746 2016.2.18 0 236 C/C++ ******************/ #include <iostream> #include<cstdio> #include<cstring> using namespace std; long long n,a[22][22],f[22][

Tags: