洛谷P1140 相似基因

题目背景

大家都知道，基因可以看作一个碱基对序列。它包含了44种核苷酸，简记作A,C,G,TA,C,G,T。生物学家正致力于寻找人类基因的功能，以利用于诊断疾病和发明药物。

在一个人类基因工作组的任务中，生物学家研究的是：两个基因的相似程度。因为这个研究对疾病的治疗有着非同寻常的作用。

题目描述

两个基因的相似度的计算方法如下：

对于两个已知基因，例如AGTGATGAGTGATG和GTTAGGTTAG，将它们的碱基互相对应。当然，中间可以加入一些空碱基-，例如：

这样,两个基因之间的相似度就可以用碱基之间相似度的总和来描述，碱基之间的相似度如下表所示：

那么相似度就是：(-3)+5+5+(-2)+(-3)+5+(-3)+5=9(−3)+5+5+(−2)+(−3)+5+(−3)+5=9。因为两个基因的对应方法不唯一，例如又有：

相似度为：(-3)+5+5+(-2)+5+(-1)+5=14(−3)+5+5+(−2)+5+(−1)+5=14。规定两个基因的相似度为所有对应方法中，相似度最大的那个。

题目描述

棋盘上 AA 点有一个过河卒，需要走到目标 BB 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 CC 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，AA 点 (0,0)(0,0)、BB 点 (n,m)(n,m)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 AA 点能够到达 BB 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 BB 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

题目背景

kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。

题目描述

这次期末考试，kkksc03 需要考 44 科。因此要开始刷习题集，每科都有一个习题集，分别有 s1,s2,s3,s4s1,s2,s3,s4 道题目，完成每道题目需要一些时间，可能不等（A1,A2,…,As1A1,A2,…,A**s1，B1,B2,…,Bs2B1,B2,…,B**s2，C1,C2,…,Cs3C1,C2,…,C**s3，D1,D2,…,Ds4D1,D2,…,D**s4）。

kkksc03 有一个能力，他的左右两个大脑可以同时计算 22 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。

洛谷 p1249 最大乘积

题目大意

---

将N分解成若干个互不相同数字之和，求乘积的最大值。

思路

---

利用 lna + lnb = ln(a + b)，将乘积的最大值转换为和的最大值。题目就可以化解为，从1, 2, 3…n中选出一些数是他们的和最大。

相当于是一个01背包问题和一个高精度乘法。

题目描述

一个正整数一般可以分为几个互不相同的自然数的和，如 3=1+23=1+2，4=1+34=1+3，5＝1+4=2+35＝1+4=2+3，6=1+5＝2+46=1+5＝2+4。

现在你的任务是将指定的正整数 nn 分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。