HDU 2476 String painter(区间DP)

String painter

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2792 Accepted Submission(s): 1272

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 change a segment of characters of a string to any other character you want. That is, after using the painter, the segment is made up of only one kind of character. Now your task is to change A to B using string painter. What’s the minimum number of operations?

Input Input contains multiple cases. Each case consists of two lines: The first line contains string A. The second line contains string B. The length of both strings will not be greater than 100.

Output A single line contains one integer representing the answer.

Sample Input zzzzzfzzzzz abcdefedcba abababababab cdcdcdcdcdcd

Sample Output 6 7

这道题目完全没有思路,看了别人的题解。方法是先求空的字符数组变成目标字符数组,再求给定的字符数组变成目标字符数组。 虽然代码很短,确很值得我去思量,第二道区间DP题目

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>

using namespace std;
int dp[105][105];
int ans[105];
char s1[105];
char s2[105];
int main()
{
    while(scanf("%s%s",s1+1,s2+1)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        int len=strlen(s1+1);
        for(int j=1;j<=len;j++)
        {
            for(int i=j;i>=1;i--)
            {
                dp[i][j]=dp[i+1][j]+1;
                for(int k=i+1;k<=j;k++)
                {
                    if(s2[k]==s2[i])
                        dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
                }
            }
        }
        for(int i=1;i<=len;i++)
            ans[i]=dp[1][i];
        for(int i=1;i<=len;i++)
        {
            if(s1[i]==s2[i])
                ans[i]=ans[i-1];
            else
            {
                for(int j=i-1;j>=1;j--)
                    ans[i]=min(ans[i],ans[j]+dp[j+1][i]);
            }
        }
        printf("%d\n",ans[len]);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

HDU 5618 Jam's problem again(三维偏序,CDQ分治,树状数组,线段树)

Jam's problem again Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 655...

528160
来自专栏算法修养

HOJ 2226&POJ2688 Cleaning Robot(BFS+TSP(状态压缩DP))

Cleaning Robot Time Limit: 1000MS Memory Limit: 65536K Total Submission...

30640
来自专栏小樱的经验随笔

POJ 2209 The King(简单贪心)

The King Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 7499...

29140
来自专栏ml

HDUOJ----剪花布条

剪花布条 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java...

364120
来自专栏数据结构与算法

POJ 2891 Strange Way to Express Integers

Description Elina is reading a book written by Rujia Liu, which introduces a ...

34870
来自专栏算法修养

POJ-1125 Stockbroker Grapevine

Stockbroker Grapevine Time Limit: 1000MS Memory Limit: 10000K Total Sub...

31840
来自专栏ml

HDUOJ-------(1022)Train Problem I

Train Problem I Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

31770
来自专栏算法修养

HDU 5157 Harry and magic string(回文树)

Harry and magic string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: ...

37580
来自专栏ml

HUDOJ-----1394Minimum Inversion Number

Minimum Inversion Number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit:...

37460
来自专栏ml

HDUOJ---The Moving Points

The Moving Points Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/...

33540

扫码关注云+社区

领取腾讯云代金券