BZOJ 1260 CQOI2007 涂色
题意：给定一个$n$长序列，你可以每次选择一段区间染色，请问从空状态转移到目标最少要多少步。
Hdu 2476 String painter
题意：给定一个$n$长序列，你可以每次选择一段区间染色，请问从初始状态$A$转移到目标$B$最少要多少步。
Codeforces 1114 D. Flood Fill
题意：给定一个$n$长序列，你要最开始选择一段连续区间，然后每次可以修改初始区间块的颜色，请问将区间变为一个颜色最少要多少步。
对于 Bzoj 1260，我们可以设$dp(i,j)$为$[i,j]$修改的最少步数。则可以列出
$$
dp(i,j)=\min(dp(i,k)+dp(k+1,j))
$$
对于$a_i=a_j$，我们可以列出
$$
dp(i,j)=\min(dp(i+1,j), dp(i,j-1))
$$
相当于$[i,j]$可以在前面先修改，可以证明这是最优的。$dp(i+1,j)$等价于$[i+1,j]$修改时可以带上$i$, 后面同理。
对于 Hdu 2476，要从初始状态出发，我们先求出 Bzoj 1260 的 DP 值，然后设$f(i)$为前$i$个位置修改的最少步数。
则
$$
f(i)=f(j)+dp(j+1,i)
$$
而对于$a_i=b_i$，那么$i$可以不涂，则
$$
f(i)=f(i-1)
$$
对于 CF 1114 D，我们必须改初始块的颜色，所以可以设$g(i,j)$为$[i,j]$修改的最小步数。
则
$$
g(i,j)=\min(g(i + 1, j), g(i, j-1))
$$
对于$a_i=a_j$，则
$$
g(i,j)=\min(g(i+1,j-1)+1)
$$
这三题都运用了区间DP的套路转移
$$
dp(i,j) \Leftarrow dp(i,k), dp(k+1,j) \\
dp(i,j) \Leftarrow dp(i+1,j), dp(i,j-1) \\
dp(i,j) \Leftarrow dp(i+1,j-1) \\
$$
以及区间覆盖的相关性质。
//BZOJ 1260
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 50 + 5, INF = 2000000000;
char gg[MAXN];
int n, dp[MAXN][MAXN], c[MAXN];
int dfs(int i, int j) {
if (i > j) return 0;
if (dp[i][j] != INF) return dp[i][j];
if (i == j) return dp[i][j] = 1;
if (c[i] == c[j]) {
dp[i][j] = min(dp[i][j], dfs(i + 1, j - 1) + 1);
dp[i][j] = min(dp[i][j], dfs(i + 1, j));
dp[i][j] = min(dp[i][j], dfs(i, j - 1));
}
for (int k = i; k < j; ++k)
dp[i][j] = min(dp[i][j], dfs(i, k) + dfs(k + 1, j));
return dp[i][j];
}
void clean() {
}
int solve() {
clean();
scanf("%s", gg + 1);
n = strlen(gg + 1);
for (int i = 1; i <= n; ++i) c[i] = gg[i] - 'A';
for (int i = 0; i <= n + 1; ++i)
for (int j = 0; j <= n + 1; ++j) dp[i][j] = INF;
cout << dfs(1, n);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
//Hdu 2476
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100 + 5, INF = 2000000000;
char a[MAXN], b[MAXN];
int n, dp[MAXN][MAXN], c[MAXN];
int f[MAXN];
int dfs(int i, int j) {
if (i > j) return 0;
if (dp[i][j] != INF) return dp[i][j];
if (i == j) return dp[i][j] = 1;
if (b[i] == b[j]) {
dp[i][j] = min(dp[i][j], dfs(i + 1, j));
dp[i][j] = min(dp[i][j], dfs(i, j - 1));
}
for (int k = i; k < j; ++k)
dp[i][j] = min(dp[i][j], dfs(i, k) + dfs(k + 1, j));
return dp[i][j];
}
void clean() {
}
int solve() {
clean();
n = strlen(a + 1);
for (int i = 0; i <= n + 1; ++i)
for (int j = 0; j <= n + 1; ++j) dp[i][j] = INF;
dfs(1, n);
f[0] = 0;
for (int i = 1; i <= n; ++i) f[i] = dp[1][i];
for (int i = 1; i <= n; ++i) {
if (a[i] != b[i]) {
for (int j = 1; j < i; ++j) {
f[i] = min(f[i], f[j] + dp[j + 1][i]);
}
} else f[i] = f[i - 1];
}
cout << f[n] << endl;
return 0;
}
}
int main() {
while (scanf("%s%s", (flyinthesky::a + 1), (flyinthesky:: b + 1)) == 2) flyinthesky::solve();
return 0;
}
//CF 1114D
//==========================Head files==========================
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
#include<map>
#define LL long long
#define db double
#define mp make_pair
#define pr pair<int, int>
#define fir first
#define sec second
#define pb push_back
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
//==========================Templates==========================
inline int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
return x * f;
}
inline LL readl() {
LL x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
return x * f;
}
int power(int a, int b) {
int ans = 1;
while (b) {
if(b & 1) ans = ans * a;
b >>= 1; a = a * a;
}
return ans;
}
int power_mod(int a, int b, int mod) {
a %= mod;
int ans = 1;
while (b) {
if(b & 1) ans = (ans * a) % mod;
b >>= 1, a = (a * a) % mod;
}
return ans;
}
LL powerl(LL a, LL b) {
LL ans = 1ll;
while (b) {
if(b & 1ll) ans = ans * a;
b >>= 1ll;a = a * a;
}
return ans;
}
LL power_modl(LL a, LL b, LL mod) {
a %= mod;
LL ans = 1ll;
while (b) {
if(b & 1ll) ans = (ans * a) % mod;
b >>= 1ll, a = (a * a) % mod;
}
return ans;
}
LL gcdl(LL a, LL b) {return b == 0 ? a : gcdl(b, a % b);}
LL abssl(LL a) {return a > 0 ? a : -a;}
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
int abss(int a) {return a > 0 ? a : -a;}
//==========================Main body==========================
#define LD "%I64d"
#define D "%d"
#define pt printf
#define sn scanf
#define pty printf("YES\n")
#define ptn printf("NO\n")
//==========================Code here==========================
const LL INF = 1152921504606846976ll;
LL n, c[5005];
LL dp[5005][5005];
LL dfs(LL i, LL j) {
if (i > j) return INF;
if (i == j) return 0;
if (dp[i][j] != INF) return dp[i][j];
if (c[i] == c[j]) dp[i][j] = min(dp[i][j], dfs(i + 1, j - 1) + 1);
else dp[i][j] = min(dfs(i, j - 1) + 1, dfs(i + 1, j) + 1);
return dp[i][j];
}
int main() {
cin >> n;
for (LL i = 1; i <= n; ++i) scanf("%lld", &c[i]);
n = unique(c + 1, c + 1 + n) - c - 1;
for (LL i = 0; i <= n + 1; ++i)
for (LL j = 0; j <= n + 1; ++j) dp[i][j] = INF;
printf("%lld\n", dfs(1, n));
return 0;
}
