hdu 2476 String Painter

时间:2023-03-09 09:28:39
hdu 2476 String Painter

第一道区间dp题,感觉题意不是很好理解

题意:一次可以转换某一个位置的字符,或是一串连续的字符,举第一个例子zzzzzfzzzzz

1:aaaaaaaaaaa

2: abbbbbbbbba

3: abcccccccba

4: abcdddddcba

5: abcdeeedcba

6: abcdefedcba

于是第一个例子输出6,第二个同理

话不多说,直接贴一波代码

 #include<cstdio>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<vector>
#include<queue>
#include<map>
#include<iterator>
#include<vector>
#include<set>
#define INF 9999999
typedef long long ll;
const int Max=(<<)+;
using namespace std; int dp[][];//dp[i][j]表示从i~j的刷法
int ans[]; int main()
{
string str1,str2;
int len;
while(cin>>str1>>str2)
{
len=str1.length();
for(int j=;j<len;j++)
{
for(int i=j;i>=;i--)
{
dp[i][j]=dp[i+][j]+;//逐个更新区间i~j内的值
for(int k=i+;k<=j;k++)
{
if(str2[i]==str2[k])//若遇到相同的则需寻找区间的最小值
dp[i][j]=min(dp[i][j],dp[i+][k]+dp[k+][j]);
}
}
} for(int i=;i<len;i++)
ans[i]=dp[][i];//ans[i]表示区间[0,i]需要刷的值
for(int i=;i<len;i++)
{
if(str1[i]==str2[i])//碰到相同的值选择不刷
ans[i]=ans[i-];
else
{
for(int j=;j<i;j++)//寻找最优解
ans[i]=min(ans[i],ans[j]+dp[j+][i]);
}
}
cout<<ans[len-]<<endl;
}
return ;
}