题目链接

题意

给你一个大串 $A$ 和若干小串 $B_i$,你可以做 $k$ 次操作:每次你可以选择从大串中删除一个小串,要求最后剩下的串尽量小,并输出长度
$lenA \leq 200,lenB_i \leq 10,m \leq 20$

题解

感觉自己做过 可惜不会做
首先我们考虑我们可以将删除操作变成删除在原串上的一段区间内和其匹配的字符串,我们考虑这种删除操作区间只可能不交或包含。不交的情况可以变成包含的情况(延长其中一个区间)
首先考虑如果能无限删除 那么就可以设 $f_{i,j}$ 表示是否能将 $[i,j]$ 区间内的串删完。考虑到之前的性质,我们有必要设 $g_{l,r,i,j}$ 表示区间 $[l,r]$ 能否被删成第 $i$ 个串的前 $j$ 个。
按照定义有 $g_{i,j,k,len_k} \to f_{i,j}$,我们只需要考虑 $j$ 怎么转移。
我们可以考虑 $r$ 这个字母是在哪里。
第一种情况:我们可以继续匹配一位,即
$$g_{l,r,i,j} = g_{l,r-1,i,j-1}$$
前提是 $B[i][j] = A[r]$
第二种情况:我们可以考虑将这个 $r$ 删除掉,即
$$g_{l,r,i,j} = g_{l,k,i,j} \& f_{k+1,r}$$
最后设 $h_i$ 表示前 $i$ 个的答案,可以直接递推:
$$h_i = \min_{j \leq i,f_{i,j} = 1} h_j + 1$$

那么现在加入了限制,我们可以考虑让 $f,g$ 都变成达到这种状态的最小步数,然后 $h$ 多加一维记录下现在操作了几次就好了。

总结

看完题解感觉就是个暴力 dp。。这种区间之间关系的题目如果有了一些性质(不存在相交,一个点最多被覆盖 x 次)之类的东西就可以很好 dp 了(可以少记很多东西)
并且还要注意这些操作的本质。。首先 $f$ 肯定很好想到的(毕竟你要求这个),但是删除的时候相当于好多段拼起来。。。所以我们需要记录对于每一个串,它匹配到了多少。大概这个思路吧
还是自己太菜了,NOIP T2 都不会,什么时候才能会这种题

代码

/*
 * Author: RainAir
 * Time: 2019-11-01 20:45:06
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 200+5;
const int MAXM = 20+5;
const int MAXL = 10+5;
int f[MAXN][MAXN],g[MAXN][MAXN][MAXM][MAXL],h[MAXN][MAXN];
char str[MAXM][MAXL],A[MAXN];
int len[MAXM];
int n,m,k;

int main(){
    freopen("a.in","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s",A+1);
    FOR(i,1,m){
        scanf("%s",str[i]+1);
        len[i] = strlen(str[i]+1);
    }
    CLR(f,0x3f);CLR(g,0x3f);
    FOR(i,1,n) FOR(j,1,m) g[i][i-1][j][0] = 0;
    FOR(len,1,n){
        FOR(l,1,n){
            int r = l+len-1;
            if(r > n) break;
            FOR(i,1,m){
                FOR(j,1,::len[i]){
                    if(str[i][j] == A[r])
                        g[l][r][i][j] = std::min(g[l][r][i][j],g[l][r-1][i][j-1]);
                    FOR(k,l,r)
                        g[l][r][i][j] = std::min(g[l][r][i][j],g[l][k-1][i][j]+f[k][r]);
                }
            }
            FOR(i,1,m) f[l][r] = std::min(f[l][r],g[l][r][i][::len[i]]+1);
        }
    }
    FOR(i,1,n){
        FOR(j,0,::k){
            h[i][j] = h[i-1][j] + 1;
            FOR(k,0,i){
                if(f[k][i] <= j) h[i][j] = std::min(h[i][j],h[k-1][j-f[k][i]]);
            }
        }
    }
    int ans = 1e9;
    FOR(i,0,k) ans = std::min(ans,h[n][i]);
    printf("%d\n",ans);
    return 0;
}


版权属于:RainAir

本文链接:https://blog.aor.sd.cn/archives/942/

转载时须注明出处及本声明

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏