首页 > 其他分享 >SP4082 MBLAST - BLAST 题解

SP4082 MBLAST - BLAST 题解

时间:2023-10-26 22:14:31浏览次数:32  
标签:right vert int 题解 空格 MBLAST SP4082 2100

几万年前做的 dp 题了,有亿点点水

题意简述

求一个字符串添加多少个空格距离最小

解法

求距离最小,可以考虑动规,其实这题的写法和最长公共子序列的写法类似。

我们设 \(f(i,j)\) 表示 \(a[1] \sim a[i]\) 和 \(b[1] \sim b[j]\) 的距离

不加空格的时候为 \(f(i,j)= f(i-1,j-1) + \left\vert a[i] - b[j]\right\vert)\);

在第一个串加空格为 \(f(i,j) = f(i-1,j) + k\);

在第二个串加空格为 \(f(i,j) = f(i,j-1) + k\);
然后我们可以发现,若都加空格相当于连个串都没有发生改变,所以状态不会转移;

所以
\(f(i,j)=\min( f(i-1,j-1) + \left\vert a[i] - b[j]\right\vert,min(f(i-1,j),f(i,j) = f(i,j-1))+k)\)。

代码如下:


#include<bits/stdc++.h>
using namespace std;
char s[2100],t[2100];
int dp[2100][2100];
int main()
{
    int k;
    scanf("%s %s %d",s+1,t+1,&k);
    int n=strlen(s+1);
    int m=strlen(t+1);
    for(int i=0;i<=n;i++)dp[i][0]=k*i;
    for(int i=0;i<=m;i++)dp[0][i]=k*i;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dp[i][j]=min(dp[i-1][j-1]+abs(s[i]-t[j]),min(dp[i-1][j],dp[i][j-1])+k);
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}

标签:right,vert,int,题解,空格,MBLAST,SP4082,2100
From: https://www.cnblogs.com/dhrwhy/p/17790567.html

相关文章

  • [AGC061A] Long Shuffle 题解
    题意给定一个满足\(A_i=i\)的排列\(A\),求对其进行一次\(\mathrm{shuffle}(1,N)\)操作后其第\(K\)项的值。其中\(\mathrm{shuffle}(L,R)\)的定义如下:若\(R=L+1\),那么交换\(A_L\)和\(A_R\)的值否则,依次执行\(\mathrm{shuffle}(L,R-1)\),\(\mathrm{shuffle}(......
  • P4678 [BalticOI 2005] Bus Trip 题解
    P4678[BalticOI2005]BusTrip题解(RE:题解再改造!!)贴码#include<bits/stdc++.h>#defineMAXN500010usingnamespacestd;//ifstreamis("trip.in",ios::in);//ofstreamos("trip.out",ios::out);//#definecinis//#definecoutosintn,m,p,t,tote......
  • [HDU 3483] A Very Simple Problem 题解
    题目描述快速求出下面式子的值:\[\left(\sum\limits_{k=1}^{N}k^{x}x^{k}\right)\bmodM\]其中\(1≤N,M≤2\times10^9\),并且\(1≤x≤50\)。题解(solution)对于该类题目,\(N\)很大,而\(x\)很小,考虑矩阵快速幂优化。对于每一个\(N\)的答案,我们用\(f(N)\)来......
  • P5537 【XR-3】系统设计 题解-哈希+线段树二分
    20231026P5537【XR-3】系统设计题解-哈希+线段树二分这个东西怎么会和哈希有关?!直接寄。Statement这个系统首先需要输入一棵\(n\)个点的有根树和一个长度为\(m\)的序列\(a\),接下来需要实现\(q\)个操作。操作分两种:1xlr表示设定起点为有根树的节点\(x\),接下来......
  • CF888E题解
    分析看到\(n\leq35\)的数据范围就想到了meet-in-middle。先爆搜出对于\(1\sim\frac{n}{2}\)和\(\frac{n}{2}\simn\)两个下标范围内在模意义下所有的和。然后用一个常见trick,就是枚举第二个部分的和,然后匹配第一个部分的和的最优解。显然匹配有两种情况,一种是......
  • chrome新版本http自动跳转https问题解决
    虽然是个好功能,但是部分内网业务还没做好https兼容,有的时候手工访问,还是变成https 解决办法:chrome://flags/找到:HTTPSUpgrades,修改disabled,重启解决,当然这个需要需要用户去调整,真正还需要服务去兼容https  ......
  • 在使用 Unity 2022 打包安卓项目时,遇到 gradle 无法访问或下载超级慢最终超时出错的问
    一般表现是打包最后一步会等待超长时间,最后报错,错误信息:PickedupJAVA_TOOL_OPTIONS:-Dfile.encoding=UTF-8FAILURE:Buildfailedwithanexception.*Whatwentwrong:Aproblemoccurredconfiguringrootproject'Gradle'.>Couldnotresolveallartifactsfor......
  • CCC 2023 题解 和 思考过程
    Trianglane水题,只要分情况判断中间和两侧有边叠牢的情况,每次减2#include<iostream>#include<cstdlib>#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>usingnamespacestd;typedeflonglongll;constintN=200010......
  • 「题解」Codeforces Round 905 (Div. 3)
    before终于有一篇题解是一次性更所有题的了。A.MorningProblemA.MorningSol&Code根据题意模拟即可。#include<bits/stdc++.h>typedeflonglongll;intmin(inta,intb){returna<b?a:b;}intmax(inta,intb){returna>b?a:b;}intT;int......
  • CF888C题解
    分析容易想到可以枚举每个字母,分别求其最小\(k\)取\(\min\)。思考对于一个\(k\),如何判其不合法。容易想到如果存在一个没有这个字符的长度大于等于\(k\)的子段,那么这个\(k\)就不合法。那么我们就知道如何求最小合法\(k\)了。找到最长的没有这个字符的子段,其长度加......