两道区间DP题目总结

发表于 分类于

CF1132F. Clear the String

题目传送门

题意：有一个字符串，每次可以删除一段连续的相同字母的子串，求删完的最小次数。

做法一

设 f[l][r]f[l][r] 表示 [l,r][l,r] 删完的最小次数，则显然转移为枚举分两段加起来取最小值。由于可以删除连续一段相同的字母，所以如果左右两端相同，无论分的两段内部如何取，一定可以钦定左边的段将左端点留到最后，右边的段将右端点留到最后（钦定最后删端点答案不变），一起删，所以答案会 −1-1。于是转移为 f[l][r]=min⁡kf[l][k]+f[k+1][r]−[sl=sr]f[l][r]=\min\limits_k f[l][k]+f[k+1][r]-[s_l=s_r]。

By cxm1024

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
int f[510][510];
signed main() {
    int n;
    string s;
    cin>>n>>s;
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<n;i++)
        f[i][i]=1;
    for(int len=2;len<=n;len++)
        for(int l=0,r=len-1;r<n;l++,r++)
            for(int k=l;k<r;k++)
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]-(s[l]==s[r]));
    cout<<f[0][n-1]<<endl;
    return 0;
}

做法二

DP 状态相同。考虑 ll 是否和另一位匹配，同时删。如果不匹配单独删，则为 1+f[l+1][r]1+f[l+1][r]，如果匹配，设匹配第 kk 位，为 f[l+1][k−1]+f[k][r]f[l+1][k-1]+f[k][r]（删完左边后，ll 和 kk 相邻，此时不需要考虑 ll）。

By kmjp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int N;
string S;
int memo[505][505];
int hoge(int L,int R) {
    if(L>=R) return 0;
    if(memo[L][R]>=0) return memo[L][R];
    int ret=1010101;
    ret=1+hoge(L+1,R);
    for(int ne=L+1;ne<R;ne++) if(S[L]==S[ne]) {
        ret=min(ret,hoge(ne,R)+hoge(L+1,ne));
    }
    return memo[L][R]=ret;
}
void solve() {
    int i,j,k,l,r,x,y; string s;
    cin>>N>>S;
    MINUS(memo);
    cout<<hoge(0,N)<<endl;
}

错解一

By Motarack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int const N = 500;
int dp[N][N];
char s[N + 1];

int main(){
    int n;
    scanf("%d%s", &n, s);
    f(i, 0, n)dp[i][i] = 1;
    f(ln, 2, n + 1)f(i, 0, n - ln + 1){
        int j = i + ln - 1, c = s[i] != s[j];
        dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + c;
    }
    printf("%d\n", dp[0][n - 1]);
}

这个解法没有区间 DP 转移，直接选择一个端点删掉，没有考虑从中间断成两半处理的情况。

错解二

By Gloid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int n,f[N][N];
char s[N];
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
#endif
    n=read();
    scanf("%s",s+1);
    memset(f,42,sizeof(f));
    for (int i=1;i<=n;i++) f[i][i]=1,f[i+1][i]=f[i][i-1]=0;
    for (int k=2;k<=n;k++)
        for (int i=1;i<=n-k+1;i++)
        {
            int j=i+k-1;
            for (int d=i;d<j;d++) f[i][j]=min(f[i][j],f[i][d]+f[d+1][j]);
            if (s[i]==s[j])
            {
                int S=1;
                for (int x=i;x<=j;x++)
                if (s[x]!=s[i])
                {
                    int t=x;
                    while (s[t+1]!=s[i]) t++;
                    S+=f[x][t];
                    x=t;
                }
                f[i][j]=min(f[i][j],S);
            }
        }
    cout<<f[1][n];
    return 0;
    //NOTICE LONG LONG!!!!!
}

他的做法为，如果这个区间左右端点相同，则把区间内用所有与其相同的位置分成若干段，每段钦定最后取这个相同的位置，这样最后可以一次操作取完。实际上这并不能保证一定最优，因为有可能会先删了中间某个与其相同的位置（即将两段合成一段），对其他位置的删除更有利，反而结果更优。

CF607B. Zuma

题目传送门

题意：有一个数组，每次可以选择回文的一段删掉，求删光的最小次数。

做法一

设 f[l][r]f[l][r] 表示删光 [l,r][l,r] 的最小次数，则显然可以从 f[l][k]+f[k+1][r]f[l][k]+f[k+1][r] 转移过来。特殊地，如果 al=ara_l=a_r，则可以由 f[l+1][r−1]f[l+1][r-1] 转移过来，只需要在最后一次删回文时顺带加上 al,ara_l,a_r 即可。

By matthew99

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int n;
int a[maxn + 5];
int dp[maxn + 5][maxn + 5];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    scanf("%d", &n);
    REP(i, 0, n) scanf("%d", a + i);
    REP(i, 0, n + 1) dp[i][i] = 0;
    REP(l, 1, n + 1)
        REP(i, 0, n - l + 1)
        {
            int j = i + l;
            dp[i][j] = oo;
            if (a[i] == a[j - 1]) dp[i][j] = dp[i + 1][j - 1];
            REP(k, i, j - 1)
                if (a[i] == a[k]) chkmin(dp[i][j], dp[i + 1][k] + dp[k + 1][j] + 1);
        }
    printf("%d\n", dp[0][n] + 1);
    return 0;
}