HDU 2476 String painter(区间dp)

时间:2023-03-09 06:00:21
HDU 2476 String painter(区间dp)

题意: 给定两个字符串,让求最少的变化次数从第一个串变到第二个串

思路: 区间dp, 直接考虑两个串的话太困难,就只考虑第二个串,求从空白串变到第二个串的最小次数,dp[i][j] 表示i->j这个区间上的最优解,那么dp[i][j] = min(dp[i + 1][j], dp[i + 1][k] + dp[k + 1][j]),这个状态转移方程中是枚举k的位置,前提是第二个串的第i个字符必须和第k个字符相等,因为这样才是求的最优的,不然的话,就没必要刷到k这个位置了。到最后在枚举每个位置,看第一个串是否与第二个串的对应位置相等,找出最优解。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = ;
int dp[maxn][maxn], ans[maxn];
char a[maxn], b[maxn];
int main()
{
while (~scanf("%s %s", a + , b + ))
{
int len = strlen(a + );
memset(dp, , sizeof(dp));
for (int i = len; i >= ; i--)
{
for (int j = i; j <= len; j++)
{
dp[i][j] = dp[i + ][j] + ;
for (int k = i + ; k <= j; k++)
if (b[i] == b[k])
dp[i][j] = min(dp[i][j], dp[i + ][k] + dp[k + ][j]);
}
}
for (int i = ; i <= len; i++)
ans[i] = dp[][i];
for (int i = ; i <= len; i++)
{
if (a[i] == b[i])
ans[i] = ans[i - ];
else//如果不等的话,就枚举每一个位置,找出一个最小的来
{
for (int j = ; j < i; j++)
ans[i] = min(ans[i], ans[j] + dp[j + ][i]);
}
}
printf("%d\n", ans[len]);
}
return ;
}