喂你脚下有坑 4年前 区间DP 回文串 微软面试给定一个字符串，每次可以删除一个连续回文，最少几次将删完字符串。 字符串删除回文串面试题 题目大意：给定一个字符串，每次可以删除一个连续回文，最少几次将删完字符串。 思路 区间DP，$dp[l][r]$ 表示删除字符串 $l\cdots r$ 需要的最小代价。 我们可以将删除回文串的过程看作不断剥离回文串两段的相同字母，因为每一次删除回文串的代价均为 1，我们可以将删除回文串的代价记在删 […] 算法竞赛 1.15k 2 1
喂你脚下有坑 7年前 区间DP 区间动规 合理合并状态 Codeforces 149D. Coloring Brackets 传送门：http://codeforces.com/contest/149/problem/D 题目翻译 一个符合匹配的括号序列，匹配的两个括号只能有一个有颜色（红色或者蓝色），相邻的符号若有颜色颜色不同。求不同的方案数。 题解 区间DP DP[left][right][lc][rc]表示left~ […] 算法竞赛 597 0 0
喂你脚下有坑 7年前 区间DP 区间动规 POJ 2955 Brackets 传送门：http://poj.org/problem?id=2955 题目翻译 有一个序列，包含((,),[,])这些内容。相应可以匹配，问最长可匹配符合字符串长度是多少。 题解 区间DP，DP[i][j]表示区间i~j的最长可匹配长度。然后区间DP转移即可。 代码 [crayon- […] 算法竞赛 587 0 0
喂你脚下有坑 7年前 icpc 区间DP 区间动规 HDOJ 5115 Dire Wolf 传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5115 题目翻译 一行有(N)只狼，第(i)只狼有攻击力(A_{i})和攻击光环(B_{i})。当消灭一只狼的时候，主角会受到这只狼左右两只狼 […] 算法竞赛 660 0 0
喂你脚下有坑 7年前 区间DP 区间动规 LightOJ 1422 Halloween Costumes 传送门：http://vjudge.net/contest/77874#problem/B 题目翻译 一个人，按顺序参加N个派对，不同的派对需要不同的服装。衣服可以新买穿/脱/套着，问至少需要新买多少件衣服。 题解 F[left][right] 表示 从第 left 天到第 right 天需要新买多 […] 算法竞赛 584 0 0
