当前位置: 首页 > 工具软件 > CybOrg > 使用案例 >

UVA - 10723 Cyborg Genes(类LCS)

逄念
2023-12-01

传送门


首先如果要求出最优解长度,实际上就是类似 L C S LCS LCS的做法,只是 L C S LCS LCS只保留公共部分作为答案,那么本题只需保存一下非公共的部分:

d [ i ] [ j ] d[i][j] d[i][j]表示字符串 s 1 s_1 s1判断到位置 i i i,字符串 s 2 s_2 s2判断到 j j j时的最短串的长度,边界是 d [ i ] [ 0 ] = d [ 0 ] [ i ] = i d[i][0]=d[0][i]=i d[i][0]=d[0][i]=i,那么有:

如果 s 1 [ i − 1 ] = = s 2 [ j − 1 ] s_1[i-1]==s_2[j-1] s1[i1]==s2[j1],有 d [ i ] [ j ] = d [ i − 1 ] [ j − 1 ] + 1 d[i][j]=d[i-1][j-1]+1 d[i][j]=d[i1][j1]+1;否则 d [ i ] [ j ] = m i n ( d [ i − 1 ] [ j ] , d [ i ] [ j − 1 ] ) + 1 d[i][j]=min(d[i-1][j],d[i][j-1])+1 d[i][j]=min(d[i1][j],d[i][j1])+1

那么该如何处理解的个数呢?这个稍微有点难想,参考了洛谷大佬的题解

f [ i ] [ j ] f[i][j] f[i][j]表示字符串 s 1 s_1 s1判断到位置 i i i,字符串 s 2 s_2 s2判断到 j j j时的最短串的个数

边界为 f [ i ] [ 0 ] = f [ 0 ] [ i ] = 1 f[i][0]=f[0][i]=1 f[i][0]=f[0][i]=1,即只看单个串,那么每个子串都作为一个解

转移过程为:

  • 如果 d [ i − 1 ] = = d [ j − 1 ] d[i-1]==d[j-1] d[i1]==d[j1],那么 f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] f[i][j]=f[i-1][j-1] f[i][j]=f[i1][j1],实际上这里判断 s 1 [ i − 1 ] = = s 2 [ j − 1 ] s_1[i-1]==s_2[j-1] s1[i1]==s2[j1]也行,在上面转移时这两个条件是等价的
  • 否则如果 d [ i − 1 ] [ j ] < d [ i ] [ j − 1 ] d[i-1][j]<d[i][j-1] d[i1][j]<d[i][j1] f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j]=f[i-1][j] f[i][j]=f[i1][j]
  • 否则如果 d [ i − 1 ] [ j ] > d [ i ] [ j − 1 ] d[i-1][j]>d[i][j-1] d[i1][j]>d[i][j1] f [ i ] [ j ] = f [ i ] [ j − 1 ] f[i][j]=f[i][j-1] f[i][j]=f[i][j1]
  • 否则 f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i ] [ j − 1 ] f[i][j]=f[i-1][j]+f[i][j-1] f[i][j]=f[i1][j]+f[i][j1],这里作和的原因是两个转移节阶段长度相同均为最短串

最后,最短串长度为 d [ n ] [ m ] d[n][m] d[n][m],解的个数为 f [ n ] [ m ] f[n][m] f[n][m]

注意使用getline读入,因为可能读入空串

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

int t,kase=0;
int d[55][55],f[55][55];
string s1,s2;

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    cin.ignore();
    while(t--){
        getline(cin,s1);
        getline(cin,s2);
        memset(d,0,sizeof d);
        memset(f,0,sizeof f);
        int m=max(s1.size(),s2.size());
        for(int i=0;i<=m;i++){
            d[i][0]=d[0][i]=i;
            f[i][0]=f[0][i]=1;
        }
        int n=s1.size();
        m=s2.size();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                if(s1[i-1]==s2[j-1]){
                    d[i][j]=d[i-1][j-1]+1;
                    f[i][j]=f[i-1][j-1];
                }else{
                    d[i][j]=min(d[i-1][j],d[i][j-1])+1;
                    if(d[i-1][j]>d[i][j-1]) f[i][j]=f[i][j-1];
                    else if(d[i-1][j]<d[i][j-1]) f[i][j]=f[i-1][j];
                    else f[i][j]=f[i-1][j]+f[i][j-1];
                }
            }
        cout<<"Case #"<<++kase<<": "<<d[n][m]<<" "<<f[n][m]<<"\n";
    }
    return 0;
}

 类似资料: