【区间DP】Zuma

我不是女神ヾ 2024-03-26 21:17 96阅读 0赞

虽然是典中典，但是不妨碍我不会

[CF607B Zuma - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][CF607B Zuma - _ _ _ _luogu.com.cn]

题意：

![09c94fc6503663cbf358a5c0bd80d6c3.png][]

思路：

首先区间DP很显然

状态设计:设dp\[l\]\[r\]为把区间\[l,r\]的所有回文串消除的最小步数

然后考虑转移

首先枚举断点k：

dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);

然后当头和尾相同的时候，分为两种情况：

当len==2&&a\[l\]==a\[r\]时，dp\[l\]\[r\]=2

否则就是

dp[l][r]=min(dp[l][r],dp[l+1][r-1]);

具体原因如下：

![62a17d0de9ca1eea9bde327965dff9d7.png][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=5e2+10;
    
    int n;
    int a[mxn],dp[mxn][mxn];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        memset(dp,0x3f,sizeof(dp));
        for(int len=1;len<=n;len++){
            for(int l=1;l+len-1<=n;l++){
                int r=l+len-1;
                if(len==1) dp[l][r]=1;
                else{
                    if(a[l]==a[r]){
                        if(r==l+1) dp[l][r]=1;
                        else dp[l][r]=min(dp[l][r],dp[l+1][r-1]);
                    }
                    for(int k=l;k<r;k++){
                        dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
                    }
                }
            }
        }
        cout<<dp[1][n]<<'\n';
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[CF607B Zuma - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/solution/CF607B
[09c94fc6503663cbf358a5c0bd80d6c3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a9fccb0fdffd432096a9bdb90141b1d7.png
[62a17d0de9ca1eea9bde327965dff9d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/88a6343ff6184e78b05b3693074175ab.png