HDU6212 区间dp 好题

拼搏现实的明天。 2022-05-12 02:08 205阅读 0赞

[传送门][Link 1]

思路：要是对原串区间dp感觉无从下手，需要重要的一步就是转化，转化成连续的01数量串，比如10010=1211

这样的话每隔一个就是同一类的。

对于单个数字，需要的就是3-a\[i\]，

对于一个区间，可以由三类转移

1. 把区间分成 两份  例如 11 00   ans=2

2.中间消去两头相遇消去  例如11 00 1  ans=1

3.三块相遇消去   例如 1 00 1 00 11   ans=2

第三种情况这三块要满足中间必须是1，两边加起来和<=3, 因为这样消去 第一个00的时候，才不会出现将1消去的情况，

然后消去第二个00，三块相遇消去

#include<bits/stdc++.h>
    using namespace std;
    
    int dp[210][210], a[210];
    char s[210];
    
    int main(){
        int T, cas=0;
        scanf("%d", &T);
        while(T--){
            scanf("%s", s);
            int len=strlen(s);
            int m=1; a[m]=1;
            for(int i=1; i<len; i++){
                if(s[i]==s[i-1]) a[m]++;
                else a[++m]=1;
            }
            memset(dp, 0x3f, sizeof dp);
    
            for(int i=1; i<=m; i++)dp[i][i]=3-a[i], dp[i][i-1]=0;
    
            for(int t=1; t<m; t++){
                for(int i=1; i+t<=m; i++){
                    int j=i+t;
                    for(int k=i; k<j; k++){
                        dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]);
                        if(t>=4 && a[k]==1 && ((k-i+1)&1) && ((j-k+1)&1) && a[i]+a[j]<=3)
                            dp[i][j]=min(dp[i][j], dp[i+1][k-1]+dp[k+1][j-1]);
                    }
                    if((t+1)&1)
                        dp[i][j]=min(dp[i][j], dp[i+1][j-1]+(a[i]+a[j]==2));
                }
            }
    
            printf("Case #%d: %d\n", ++cas, dp[1][m]);
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6212

发表评论取消回复

表情：

评论列表（有 0 条评论，205人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 2476 String painter（两次区间dp）

String painter Problem Description There are two strings A and B with equal

ゝ一世哀愁。/ 2024年02月17日 19:36/ 0 赞/ 57 阅读

相关 HDU 4632 回文串（区间dp）

Palindrome subsequence Problem Description In mathematics, a subsequence is

比眉伴天荒/ 2024年02月17日 19:34/ 0 赞/ 24 阅读

相关区间dp

概念区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的dp算法。借鉴大佬总结：[猛戳][Link

Bertha 。/ 2023年07月10日 08:18/ 0 赞/ 43 阅读

相关 Brackets (区间DP)

目录 Brackets (区间DP) 题目题意思路题解 Brackets (区间DP)

绝地灬酷狼/ 2023年06月01日 06:11/ 0 赞/ 33 阅读

相关区间dp问题

区间dp一般有以下几种类型的题目：如何将环形区间问题转换为线性dp问题如何记录方案数目区间dp与高精度的结合高维区间dp问题一般区间dp有

浅浅的花香味﹌/ 2022年09月12日 12:54/ 0 赞/ 238 阅读

相关 HDU5900（区间DP）

QSC and Master Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072

た入场券/ 2022年05月30日 11:41/ 0 赞/ 254 阅读

相关 HDU 6365 Shoot Game区间dp+离散化

[传送门][Link 1] 这个题跟UVALive - 6938，的思路是一样的，感觉没做过那个题，这个题真的不好想。具体思路可以看 [\-》这个题][-] 然后这个题就

叁歲伎倆/ 2022年05月17日 12:11/ 0 赞/ 197 阅读

相关 HDU6212 区间dp 好题

[传送门][Link 1] 思路：要是对原串区间dp感觉无从下手，需要重要的一步就是转化，转化成连续的01数量串，比如10010=1211 这样的话每隔一个就是同一类的。

拼搏现实的明天。/ 2022年05月12日 02:08/ 0 赞/ 206 阅读

相关区间dp入门

概念：区间DP就是区间上的DP，先算出小区间的最优解，再由小区间合并推出大区间的最优解。典例：一、石子合并。 1.[51Nod 1021 石子归并]

深藏阁楼爱情的钟/ 2022年03月19日 07:07/ 0 赞/ 325 阅读

相关区间dp

让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度len为每次分割成的小

小鱼儿/ 2021年11月26日 19:50/ 0 赞/ 463 阅读