ACS 2022寒假第一周周练

ACS 2022寒假第一周周练

文章目录

A. Burglar and Matches

题目大意分析代码 B.Goldbach's Conjecture

题目大意分析代码 C.Balance

题目大意分析拓展代码 D.Monitor

题目大意分析代码 E.Radar Installation

题目大意分析代码 F.Human Gene Functions

题目大意分析相关代码

---

A. Burglar and Matches 题目大意

原题链接
窃贼带着一个容量为 n ( 1 ≤ n ≤ 2 ∗ 1 0 8 ) n(1leq n leq 2*10^8) n(1≤n≤2∗108)的背包进入一个火柴仓库，仓库中有 m ( 1 ≤ m ≤ 20 ) m(1leq m leq 20) m(1≤m≤20)个货架，第 i i i个货架上有 a i ( 1 ≤ a i ≤ 1 0 8 ) a_i(1leq a_i leq 10^8) ai​(1≤ai​≤108)个火彩盒，每盒有 b i ( 1 ≤ b i ≤ 20 ) b_i(1leq b_i leq 20) bi​(1≤bi​≤20)根火柴 ( 即 每 个 货 架 上 的 火 柴 盒 内 的 火 柴 根 数 是 相 同 的 ) (即每个货架上的火柴盒内的火柴根数是相同的) (即每个货架上的火柴盒内的火柴根数是相同的)，问这名窃贼最多可以拿走多少根火柴。

分析  |贪心

在这名窃贼的眼中，他的背包只有 n ( 1 ≤ n ≤ 2 ∗ 1 0 8 ) n(1leq n leq 2*10^8) n(1≤n≤2∗108)个口袋，每个口袋只能容纳一盒火柴，所以他为了保证自己可以拿走最多的火柴，自然会优先选择装有火柴数最多的火柴盒，这也就是贪心的思路。
具体的 *** 作就是对货架依照 b i b_i bi​大小进行排序，然后依次对每个货架进行访问，令背包装有火柴数为 s u m sum sum, s u m sum sum初始值为0：
1.若可以直接取完当前货架上所有的火柴盒，则 s u m + = a i ∗ b i sum+=a_i*b_i sum+=ai​∗bi​
2.若无法取完当前货架上所有的火柴盒，则 s u m + = 剩 余 口 袋 数 ∗ b i sum+=剩余口袋数*b_i sum+=剩余口袋数∗bi​

代码

#include
using namespace std;
typedef long long ll;
ll n,m,sum;
struct node{
	ll x,y;//x表示货架上的火柴数，y表示火柴盒内的火柴数
};
node a[25];
int cmp(node a,node b){
	return a.y>n>>m;
	for(int i=0;i>a[i].x>>a[i].y;
	}
	sort(a,a+m,cmp);//第三个参数表示排序的规则，默认从小到大，也可以由自己定义
	for(int i=m-1;i>=0;i--){//对取火柴盒过程的模拟
		if(n-a[i].x<=0){
			sum+=a[i].y*n;
			break;
		}
		else{
			n-=a[i].x;
			sum+=a[i].x*a[i].y;
		}
	}
	cout< 
 
B.Goldbach’s Conjecture 
题目大意 
原题链接
 哥德巴赫猜想：任何一个大于
     
      
       
        
         4
        
       
       
        4
       
      
     4的偶数都可以表示为两个奇质数的和。
 先给定一个大于
    
     
      
       
        4
       
      
      
       4
      
     
    4的偶数
    
     
      
       
        n
       
       
        (
       
       
        6
       
       
        ≤
       
       
        n
       
       
        <
       
       
        1
       
       
        
         0
        
        
         6
        
       
       
        )
       
      
      
       n(6leq n< 10^6)
      
     
    n(6≤n<106)，问是否存在一个满足要求的奇质数对：
 如果不存在则输出
    
     
      
       
        G
       
       
        o
       
       
        l
       
       
        d
       
       
        b
       
       
        a
       
       
        c
       
       
        
         h
        
        
         ′
        
       
       
        s
       
       
         
       
       
        c
       
       
        o
       
       
        n
       
       
        j
       
       
        e
       
       
        c
       
       
        t
       
       
        u
       
       
        r
       
       
        e
       
       
         
       
       
        i
       
       
        s
       
       
         
       
       
        w
       
       
        r
       
       
        o
       
       
        n
       
       
        g
       
       
        .
       
      
      
       Goldbach's conjecture is wrong.
      
     
    Goldbach′s conjecture is wrong.
 如果存在多个，则输出绝对值相差最大的一对，且结果中要求先输出较小数。
 
分析 
 | 素数打表 
我们默认哥德巴赫猜想是正确的，将其作为结论来使用。
 这道题的思路是对奇质数的枚举，在式子
    
     
      
       
        n
       
       
        =
       
       
        a
       
       
        +
       
       
        b
       
      
      
       n=a+b
      
     
    n=a+b中，若我们已知
    
     
      
       
        a
       
      
      
       a
      
     
    a是一个奇质数，那么我们只需要判断
    
     
      
       
        b
       
      
      
       b
      
     
    b是否同样为奇质数，如果是则可以直接输出结果，如果不是则继续枚举。
 
最大的问题是超时
 
每次枚举都需要判断一次
    
     
      
       
        b
       
      
      
       b
      
     
    b，所以我们第一思路是拿空间换时间；
 但如果是用暴力循环计算素数的情况，仍然会超时，改进为埃氏筛后可以简化时间，就不会超时，还可以进一步优化为欧拉筛。
 具体内容可以见于质数筛法
 
代码 
#include
#include
using namespace std;
const int N=1000005;
typedef long long ll;
int prim[N];
int a[N];
int cnt;
int n;
void f1(){//暴力循环，超时 
	a[0]=2;a[1]=3;
	cnt+=2;
	prim[2]=prim[3]=1;
	for(int i=4;itmp){
			a[cnt++]=i;prim[i]=1;
		}
	}
}
void f2(){//埃氏筛，任一合数仅能被唯一分解成有限个素数的乘积
	for(int i=0;i>n&&n){
		for(int i=1;i<=cnt;i++){
			if(prim[n-a[i]]){
				cout< 
C.Balance 
题目大意 
原题链接
 有一个杠杆，先给定
    
     
      
       
        C
       
       
        (
       
       
        2
       
       
        ≤
       
       
        C
       
       
        ≤
       
       
        20
       
       
        )
       
      
      
       C(2leq C leq 20)
      
     
    C(2≤C≤20)个钩子的位置，再给定
    
     
      
       
        G
       
       
        (
       
       
        2
       
       
        ≤
       
       
        G
       
       
        ≤
       
       
        20
       
       
        )
       
      
      
       G(2leq G leq 20)
      
     
    G(2≤G≤20)个砝码的质量，质量最大为
    
     
      
       
        25
       
      
      
       25
      
     
    25,问有多少种方法可以在使用所有砝码的前提上使杠杆平衡。
 
分析 
 | 01背包 杠杆平衡的条件就是： 动力臂*动力=阻力臂*阻力 
对于每个砝码来说有
    
     
      
       
        C
       
      
      
       C
      
     
    C个位置可以选择，如果直接采用暴力搜索的方法，枚举出所有排列的可能，时间复杂度就是
    
     
      
       
        O
       
       
        (
       
       
        2
       
       
        
         0
        
        
         20
        
       
       
        )
       
      
      
       O(20^{20})
      
     
    O(2020)，这当然是会超时的，所以我们需要进一步分析题目。
 
我们最终的目标是求出在放置好
    
     
      
       
        G
       
      
      
       G
      
     
    G个砝码的前提下，有多少种满足要求的方法，
 若我们已知在放好
    
     
      
       
        G
       
       
        −
       
       
        1
       
      
      
       G-1
      
     
    G−1个砝码后杠杆将会面临的所有情况以及达到对应情况的方法数，就可以进一步得知放置第
    
     
      
       
        G
       
      
      
       G
      
     
    G个砝码后杠杆将会面临的所有情况以及达到对应情况的方法数，这就实现了对问题的分解。
 
步骤一：确定状态
 步骤二：确定状态转移方程
 步骤三：确定边界情况和初始条件
 步骤四：确定计算顺序
 
步骤一：确定状态
 在问题的分解中，一个状态有两个因素：当前放置砝码个数、杠杆所处于的情况。所以不妨以
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       dp[i][j]
      
     
    dp[i][j]来表示放置好
     
      
       
        
         i
        
       
       
        i
       
      
     i个砝码后杠杆处于情况
     
      
       
        
         j
        
       
       
        j
       
      
     j的方法数。
 

    
     
      
       
        j
       
      
      
       j
      
     
    j表示杠杆所处的状态，即平衡情况，与杠杆左右力矩
    
     
      
       
        (
       
       
        力
       
       
        与
       
       
        力
       
       
        臂
       
       
        之
       
       
        积
       
       
        )
       
      
      
       (力与力臂之积)
      
     
    (力与力臂之积)有关，由于坐标的设置存在负数，所以不妨认为当
    
     
      
       
        j
       
       
        <
       
       
        0
       
      
      
       j<0
      
     
    j<0时，杠杆向左倾斜；当
    
     
      
       
        j
       
       
        >
       
       
        0
       
      
      
       j>0
      
     
    j>0时，杠杆向右倾斜；
    
     
      
       
        j
       
       
        =
       
       
        0
       
      
      
       j=0
      
     
    j=0时，杠杆恰处于平衡状态。而
    
     
      
       
        j
       
      
      
       j
      
     
    j的绝对值大小正反映了杠杆的倾斜情况。
 但此时又暴露了另外一个问题，二维数组下标为负数
    
     
      
       
        （
       
       
        需
       
       
        要
       
       
        注
       
       
        意
       
       
        的
       
       
        是
       
       
        ，
       
       
        在
       
       
        C
       
       
        语
       
       
        言
       
       
        中
       
       
        ，
       
       
        形
       
       
        如
       
      
      
       （需要注意的是，在C语言中，形如
      
     
    （需要注意的是，在C语言中，形如a[2][-2]
    
     
      
       
        的
       
       
        表
       
       
        达
       
       
        不
       
       
        会
       
       
        报
       
       
        错
       
       
        ，
       
       
        因
       
       
        为
       
       
        线
       
       
        性
       
       
        存
       
       
        储
       
       
        ，
       
       
        这
       
       
        个
       
       
        与
       
      
      
       的表达不会报错，因为线性存储，这个与
      
     
    的表达不会报错，因为线性存储，这个与a[1]
    
     
      
       
        中
       
       
        倒
       
       
        数
       
       
        第
       
       
        二
       
       
        个
       
       
        元
       
       
        素
       
       
        的
       
       
        位
       
       
        置
       
       
        是
       
       
        一
       
       
        致
       
       
        的
       
       
        ）
       
      
      
       中倒数第二个元素的位置是一致的）
      
     
    中倒数第二个元素的位置是一致的）但在此处会影响我们的递推过程，所以我们要重新确定平衡点。
 根据题目要求，最多有20个砝码，每个最重为25，且最远置于刻度15的位置，所以力矩的最大值为
    
     
      
       
        7500
       
       
        =
       
       
        20
       
       
        ∗
       
       
        25
       
       
        ∗
       
       
        15
       
      
      
       7500=20*25*15
      
     
    7500=20∗25∗15，本来
    
     
      
       
        j
       
      
      
       j
      
     
    j的范围是
    
     
      
       
        (
       
       
        −
       
       
        7500
       
       
        —
       
       
        —
       
       
        0
       
       
        —
       
       
        —
       
       
        7500
       
       
        )
       
      
      
       (-7500——0——7500)
      
     
    (−7500——0——7500)，为了不影响递推，全部右移
    
     
      
       
        7500
       
      
      
       7500
      
     
    7500位，
    
     
      
       
        j
       
      
      
       j
      
     
    j的范围变为
    
     
      
       
        (
       
       
        0
       
       
        —
       
       
        —
       
       
        7500
       
       
        —
       
       
        —
       
       
        15000
       
       
        )
       
      
      
       (0——7500——15000)
      
     
    (0——7500——15000)
 
步骤二：确定状态转移方程
 对于第
    
     
      
       
        i
       
      
      
       i
      
     
    i个砝码来说，有
    
     
      
       
        C
       
      
      
       C
      
     
    C个位置可以选择，也就意味着它对杠杆有
    
     
      
       
        C
       
      
      
       C
      
     
    C种不同的影响。
 若选择了第
    
     
      
       
        k
       
      
      
       k
      
     
    k个位置，则有递推公式：
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        +
       
       
        c
       
       
        [
       
       
        k
       
       
        ]
       
       
        ∗
       
       
        g
       
       
        [
       
       
        i
       
       
        ]
       
       
        ]
       
       
        +
       
       
        =
       
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        −
       
       
        1
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       dp[i][j+c[k]*g[i]]+=dp[i-1][j]
      
     
    dp[i][j+c[k]∗g[i]]+=dp[i−1][j]
 状态
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        +
       
       
        c
       
       
        [
       
       
        k
       
       
        ]
       
       
        ∗
       
       
        g
       
       
        [
       
       
        i
       
       
        ]
       
       
        ]
       
      
      
       dp[i][j+c[k]*g[i]]
      
     
    dp[i][j+c[k]∗g[i]]的方法数不仅有原先
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        +
       
       
        c
       
       
        [
       
       
        k
       
       
        ]
       
       
        ∗
       
       
        g
       
       
        [
       
       
        i
       
       
        ]
       
       
        ]
       
      
      
       dp[i][j+c[k]*g[i]]
      
     
    dp[i][j+c[k]∗g[i]]包含的方法数，还需要加上由
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        −
       
       
        1
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       dp[i-1][j]
      
     
    dp[i−1][j]所包含的方法数，因为可以状态转移，通过放置砝码抵达当前状态。
 
步骤三：确定边界情况和初始条件
 根据题目显示，当不存在砝码的时候，杠杆同样处于平衡情况，所以初始条件为
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        0
       
       
        ]
       
       
        [
       
       
        7500
       
       
        ]
       
       
        =
       
       
        1
       
       
        。
       
      
      
       dp[0][7500]=1。
      
     
    dp[0][7500]=1。
 
步骤四：确定计算顺序
 计算顺序如下
 
for(int j=0;j<=15000;j++){
	for(int k=1;k<=C;k++){
		dp[i][j+c[k]*g[i]]+=dp[i-1][j];
	}
}
 
但其中包含了对不可能情况的讨论，比如说当
    
     
      
       
        j
       
      
      
       j
      
     
    j大于
    
     
      
       
        15000
       
      
      
       15000
      
     
    15000的情况，或者是
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        −
       
       
        1
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       dp[i-1][j]
      
     
    dp[i−1][j]为
    
     
      
       
        0
       
      
      
       0
      
     
    0的情况，这些都没有继续讨论的意义，所以可以对其进行优化
 
for(int j=0;j<=15000;j++){
	if(dp[i-1][j]){//仅考虑有意义的情况
		for(int k=1;k<=C;k++){
			dp[i][j+c[k]*g[i]]+=dp[i-1][j];
		}
	}
}
 
拓展 
2021年第十二届蓝桥杯省赛B组（C/C++）试题G——砝码称重
 大意是说有一架天平和
    
     
      
       
        n
       
       
        (
       
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        100
       
       
        )
       
      
      
       n(1leq n leq 100)
      
     
    n(1≤n≤100)个砝码，问通过灵活的使用砝码，这个天平可以称出多少种不同的质量。
 这同样是一道01背包的题目——题解。
 
关于一些背包问题的介绍可以看看这篇博客——背包九讲
 
代码 
#include
#include
#include
using namespace std;
int C,G;
int c[25],g[25];
int dp[25][15005]; 
int DP[15005];//作为例子，说明一维优化的条件 
int main(){
	cin>>C>>G;
	for(int i=1;i<=C;i++){
		cin>>c[i];
	}
	for(int i=1;i<=G;i++){
		cin>>g[i];
	}
	dp[0][7500]=1;
	for(int i=1;i<=G;i++){
		for(int j=0;j<=15000;j++){
			if(dp[i-1][j]){
				for(int k=1;k<=C;k++){
					dp[i][j+c[k]*g[i]]+=dp[i-1][j];
				}
			}
		}
	}
	cout< 
 
D.Monitor 
题目大意 
原题链接
 原先显示器的尺寸为
    
     
      
       
        a
       
       
        ∗
       
       
        b
       
      
      
       a*b
      
     
    a∗b，如今要把尺寸改为满足
    
     
      
       
        
         a
        
        
         b
        
       
       
        =
       
       
        
         x
        
        
         y
        
       
      
      
       frac{a}{b}=frac{x}{y}
      
     
    ba​=yx​，同时要使得显示器的面积尽可能的大。
    
     
      
       
        (
       
       
        1
       
       
        ≤
       
       
        a
       
       
        ,
       
       
        b
       
       
        ,
       
       
        x
       
       
        ,
       
       
        y
       
       
        ≤
       
       
        2
       
       
        ∗
       
       
        1
       
       
        
         0
        
        
         9
        
       
       
        )
       
      
      
       (1leq a,b,x,y leq 2*10^9)
      
     
    (1≤a,b,x,y≤2∗109)
 
分析 
思路很直观，但需要注意的是给定的
    
     
      
       
        x
       
       
        ,
       
       
        y
       
      
      
       x,y
      
     
    x,y可能比
    
     
      
       
        a
       
       
        ,
       
       
        b
       
      
      
       a,b
      
     
    a,b还大，所以需要先把
    
     
      
       
        x
       
       
        ,
       
       
        y
       
      
      
       x,y
      
     
    x,y化为最简比，也就是同时除以最大公约数，求最大公约数的方法是——辗转相除法
 
int gcd(int a,int b){
	return (b)?gcd(b,a%b):a;
}
 
然后再根据
    
     
      
       
        t
       
       
        =
       
       
        m
       
       
        i
       
       
        n
       
       
        (
       
       
        
         a
        
        
         x
        
       
       
        ,
       
       
        
         b
        
        
         y
        
       
       
        )
       
      
      
       t=min(frac{a}{x},frac{b}{y})
      
     
    t=min(xa​,yb​)确定比值，最后输出结果。
 
代码 
#include
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
	return (b)?gcd(b,a%b):a;
}
int main(){
	ll a,b,x,y;
	cin>>a>>b>>x>>y;
	int tmp=gcd(x,y);
	x/=tmp;
	y/=tmp;
	int t=min(a/x,b/y);
	cout<<(t*x)<<" "<<(t*y);
}
 
 
E.Radar Installation 
题目大意 
原题链接
 将海岸线作为
    
     
      
       
        x
       
      
      
       x
      
     
    x轴，而雷达只能放在
    
     
      
       
        x
       
      
      
       x
      
     
    x轴上。
 海岸线上可以放置扫描半径为
    
     
      
       
        R
       
      
      
       R
      
     
    R的雷达，给定
    
     
      
       
        n
       
       
        (
       
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        1000
       
       
        )
       
      
      
       n(1leq nleq 1000)
      
     
    n(1≤n≤1000)座岛屿的位置坐标(不考虑海岛的半径)，问最少需要多少个雷达装置可以实现对海岛的全覆盖扫描。
 若不存在满足要求的方案则输出
    
     
      
       
        −
       
       
        1
       
      
      
       -1
      
     
    −1。
 
分析 
 |贪心 
设岛屿的坐标为
    
     
      
       
        (
       
       
        x
       
       
        ,
       
       
        y
       
       
        )
       
      
      
       (x,y)
      
     
    (x,y)，雷达扫描半径为
    
     
      
       
        r
       
      
      
       r
      
     
    r，出现
    
     
      
       
        r
       
       
        <
       
       
        y
       
      
      
       r 若所有的岛屿均可以被雷达所扫描到，接下来就是分析在何种情况下所需雷达数目最少。
 其实也就是让每个雷达尽可能覆盖最多的岛屿，且雷达所覆盖的岛屿不要发生重叠。
 
正难则反，从雷达角度考虑如果不好思考，就反过来从岛屿出发，对于位于
    
     
      
       
        (
       
       
        x
       
       
        ,
       
       
        y
       
       
        )
       
      
      
       (x,y)
      
     
    (x,y)的岛屿来说，只要雷达在区间
    
     
      
       
        [
       
       
        x
       
       
        −
       
       
        
         
          
           r
          
          
           2
          
         
         
          −
         
         
          
           y
          
          
           2
          
         
        
       
       
        ,
       
       
        x
       
       
        +
       
       
        
         
          
           r
          
          
           2
          
         
         
          −
         
         
          
           y
          
          
           2
          
         
        
       
       
        ]
       
      
      
       [x-sqrt{r^2-y^2},x+sqrt{r^2-y^2}]
      
     
    [x−r2−y2
           ​,x+r2−y2
           ​]之间，就可以被扫描。
 将岛屿依据
    
     
      
       
        x
       
       
        +
       
       
        
         
          
           r
          
          
           2
          
         
         
          −
         
         
          
           y
          
          
           2
          
         
        
       
      
      
       x+sqrt{r^2-y^2}
      
     
    x+r2−y2
           ​进行从小到大的排序，之后把雷达插入。
 排好序后，第一座雷达首先放在
    
     
      
       
        
         x
        
        
         0
        
       
       
        +
       
       
        
         
          
           r
          
          
           2
          
         
         
          −
         
         
          
           y
          
          
           0
          
          
           2
          
         
        
       
      
      
       x_0+sqrt{r^2-y_0^2}
      
     
    x0​+r2−y02​
           ​处，若此时下一座岛屿仍然可以被这个雷达扫描到，则继续访问下一座岛屿；若下一座岛屿无法被扫描到，我们就需要重新放置下一个雷达，而这个雷达的位置选择则要依循之前的贪心思想：雷达所覆盖的岛屿不要发生重叠，所以这个雷达要放置在
    
     
      
       
        
         x
        
        
         1
        
       
       
        +
       
       
        
         
          
           r
          
          
           2
          
         
         
          −
         
         
          
           y
          
          
           1
          
          
           2
          
         
        
       
      
      
       x_1+sqrt{r^2-y_1^2}
      
     
    x1​+r2−y12​
           ​处。
 
代码 
#include
#include
#include
using namespace std;
typedef long long ll;
struct node{
	double x,y;
};
node a[1005];
int n,R,cnt;
int ans;
bool cover(node t,double X){
	double tmpx=(X-t.x)*(X-t.x);
	double tmpy=t.y*t.y;
	if(tmpx+tmpy<=R*R)return true;
	else return false;
}
double f(node a){
	double tmp=sqrt(R*R-a.y*a.y)+a.x;
	return tmp;
}
int cmp(node a,node b){
	return f(a)>n>>R&&(n+R)){
		ans=0;
		for(int i=0;i>a[i].x>>a[i].y;
			if(a[i].y>R)ans=-1;
		}
		if(ans==-1)cout<<"Case "<<(++cnt)<<": -1"< 
F.Human Gene Functions 
题目大意 
原题链接
 给定两个碱基序列，需要输出序列间的最大相似度。
 关于相似度的定义参照题目给定样例。
 
分析 
 |动态规划 
两条序列要通过一种恰当的配对方式使得相似度最高，首先要确定一定不会出现
    
     
      
       
        
        
         ′
        
       
       
        
         −
        
        
         ′
        
       
      
      
       '-'
      
     
    ′−′与
    
     
      
       
        
        
         ′
        
       
       
        
         −
        
        
         ′
        
       
      
      
       '-'
      
     
    ′−′配对的情况；其次，暴力枚举也不可行，
    
     
      
       
        
        
         ′
        
       
       
        
         −
        
        
         ′
        
       
      
      
       '-'
      
     
    ′−′的位置选择以及两两配对的可能情况过多。所以我们选择动态规划来处理问题。
 
步骤一：确定状态
 步骤二：确定状态转移方程
 步骤三：确定边界情况和初始条件
 步骤四：确定计算顺序
 
步骤一：确定状态
 最后输出的结果是长度为
    
     
      
       
        x
       
      
      
       x
      
     
    x和
    
     
      
       
        y
       
      
      
       y
      
     
    y的序列的最大相似度，不妨以
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        x
       
       
        ]
       
       
        [
       
       
        y
       
       
        ]
       
      
      
       dp[x][y]
      
     
    dp[x][y]来表示这个值。
 步骤二：确定状态转移方程
 若我们想要求出
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       dp[i][j]
      
     
    dp[i][j]的值，也就是长度为
    
     
      
       
        i
       
      
      
       i
      
     
    i和
    
     
      
       
        j
       
      
      
       j
      
     
    j的序列的最大相似度，而这个状态可以由三种状态所转移过来，分别是：
 1.
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        −
       
       
        1
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       dp[i-1][j]
      
     
    dp[i−1][j]，第
    
     
      
       
        i
       
      
      
       i
      
     
    i个碱基与
    
     
      
       
        
        
         ′
        
       
       
        
         −
        
        
         ′
        
       
      
      
       '-'
      
     
    ′−′配对所得结果；
 2.
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        −
       
       
        1
       
       
        ]
       
      
      
       dp[i][j-1]
      
     
    dp[i][j−1]，第
    
     
      
       
        j
       
      
      
       j
      
     
    j个碱基与
    
     
      
       
        
        
         ′
        
       
       
        
         −
        
        
         ′
        
       
      
      
       '-'
      
     
    ′−′配对所得结果；
 3.
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        −
       
       
        1
       
       
        ]
       
       
        [
       
       
        j
       
       
        −
       
       
        1
       
       
        ]
       
      
      
       dp[i-1][j-1]
      
     
    dp[i−1][j−1]，第
    
     
      
       
        i
       
      
      
       i
      
     
    i个碱基与第
    
     
      
       
        j
       
      
      
       j
      
     
    j个碱基所得结果；
 为了满足最优解，我们将从中选择最大值作为
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
      
      
       dp[i][j]
      
     
    dp[i][j]的值，状态转移方程就是：
 
    
     
      
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
       
        =
       
       
        m
       
       
        a
       
       
        x
       
       
        (
       
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        −
       
       
        1
       
       
        ]
       
       
        [
       
       
        j
       
       
        ]
       
       
        +
       
       
        m
       
       
        [
       
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
       
        ]
       
       
        
         [
        
        
         ′
        
       
       
        
         −
        
        
         ′
        
       
       
        ]
       
       
        ,
       
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        ]
       
       
        [
       
       
        j
       
       
        −
       
       
        1
       
       
        ]
       
       
        +
       
       
        m
       
       
        
         [
        
        
         ′
        
       
       
        
         −
        
        
         ′
        
       
       
        ]
       
       
        [
       
       
        b
       
       
        [
       
       
        j
       
       
        ]
       
       
        ]
       
       
        ,
       
       
        d
       
       
        p
       
       
        [
       
       
        i
       
       
        −
       
       
        1
       
       
        ]
       
       
        [
       
       
        j
       
       
        −
       
       
        1
       
       
        ]
       
       
        +
       
       
        m
       
       
        [
       
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
       
        ]
       
       
        [
       
       
        b
       
       
        [
       
       
        j
       
       
        ]
       
       
        ]
       
       
        )
       
      
      
       dp[i][j]=max(dp[i-1][j]+m[a[i]]['-'],dp[i][j-1]+m['-'][b[j]],dp[i-1][j-1]+m[a[i]][b[j]])
      
     
    dp[i][j]=max(dp[i−1][j]+m[a[i]][′−′],dp[i][j−1]+m[′−′][b[j]],dp[i−1][j−1]+m[a[i]][b[j]])
 步骤三：确定边界情况和初始条件
 边界条件也就是当有一条序列长度为0时，可以直接求出此时的最大相似度。
 步骤四：确定计算顺序
 根据状态转移方程可以看出计算顺序为自左向右，自上往下。
 
相关 
最长公共子序列
 两道题的思路其实是一致的，这道可以作为练习做一下。
 
代码 
#include
#include
using namespace std;
typedef long long ll;
int m[128][128];
int t;
int x,y;
char a[105],b[105];
int dp[105][105]; 
void init(){
	memset(dp,0,sizeof dp);
	memset(a,0,sizeof a);
	memset(b,0,sizeof b);
	cin>>x;
	cin>>a+1;
	cin>>y;
	cin>>b+1;
}
int main(){
	
	m['A']['A']=5;
	m['C']['C']=5;
	m['G']['G']=5;
	m['T']['T']=5;
	m['-']['-']=-505;
	m['A']['C']=m['C']['A']=-1;
	m['A']['G']=m['G']['A']=-2;
	m['A']['T']=m['T']['A']=-1;
	m['A']['-']=m['-']['A']=-3;
	m['C']['G']=m['G']['C']=-3;
	m['C']['T']=m['T']['C']=-2;
	m['C']['-']=m['-']['C']=-4;
	m['G']['T']=m['T']['G']=-2;
	m['G']['-']=m['-']['G']=-2;
	m['T']['-']=m['-']['T']=-1;
	
	cin>>t;
	while(t--){
		init();
		for(int i=1;i<=x;i++)
			dp[i][0]=dp[i-1][0]+m[a[i]]['-'];  		
		for(int j=1;j<=y;j++)
			dp[0][j]=dp[0][j-1]+m['-'][b[j]];
		for(int i=1;i<=x;i++)
			for(int j=1;j<=y;j++){
				int tmp1=dp[i-1][j]+m[a[i]]['-'];
			    int tmp2=dp[i][j-1]+m['-'][b[j]];
			    int tmp3=dp[i-1][j-1]+m[a[i]][b[j]];
			    dp[i][j]=max(tmp1,max(tmp2,tmp3));
			}
		cout< 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5710560.html