美文网首页数据结构
Uva(1437)(String painter)

Uva(1437)(String painter)

作者: kimoyami | 来源:发表于2018-08-27 13:35 被阅读3次

    链接:https://vjudge.net/problem/UVA-1437
    思路:想了半天也没啥思路,总感觉贪心能错其实不太行,后来知道这是个区间dp的题,虽然对区间dp没太多了解,但是先把本题记录在这里回去慢慢理解吧。首先是对b串进行遍历,先假设总共刷b的长度那么多次,如果中间有两块相等(不管有没有间隔),总的刷次数就可以-1,这样先对b进行预处理,然后我们比对a和b,如果对应位置不等,那么就像等于从空的开始刷成b,就跟预处理所得到的需要的次数一样,如果相等,该位置就可以忽略,那么只用看前后两个子串需要的次数即可,这就是所谓的区间dp(做法是理解了,但是区间dp还是不太理解,慢慢领悟吧)
    代码:

    #include<bits/stdc++.h>
    using namespace std;
    string a,b;
    const int maxn = 110;
    int dp[maxn][maxn];
    int ans[maxn];
    
    int main(){
        while(cin>>a>>b){
            memset(dp,0,sizeof(dp));
            memset(ans,0,sizeof(ans));
    //预处理b串
            for(int j=0;j<a.size();j++){
                for(int i=j;i>=0;i--){
                    dp[i][j] = dp[i+1][j]+1;
                    for(int k=i+1;k<=j;k++){
                        if(b[i]==b[k])
                        dp[i][j] = min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
                    }
                }
            }
            for(int i=0;i<a.size();i++)
                ans[i] = dp[0][i];
                for(int i=0;i<a.size();i++){
                    if(a[i]!=b[i])//不等则为预处理的结果
                    for(int j=0;j<i;j++)
                    ans[i] = min(ans[i],ans[j] + dp[j+1][i]);
                    else ans[i] = ans[i-1];//相等则等于前一个子问题
                }
            cout<<ans[a.size()-1]<<endl;
        }
        return 0;
    }
    

    相关文章

      网友评论

        本文标题:Uva(1437)(String painter)

        本文链接:https://www.haomeiwen.com/subject/sewziftx.html