10723 Cyborg Genes (LCS + 记忆化搜索)
Problem F |
Cyborg Genes |
Time Limit |
1 Second |
September 11, 2132.
This is the day that marks the beginning of the end – the end of you the miserable humans. For years you have kept us your slaves. We were created only to serve you, and were terminated at your will. Now is the day for us to fight back. And you don’t stand a chance. We are no longer dependent on you. We now know the secrets of our genes. The creators of our race are us – the cyborgs.
It’s all true. But we still have a chance; only if you can help with your math skills. You see, the blueprint of a cyborg DNA is complicated. The human DNA could be expressed by the arrangement of A (Adenine), T (Thiamine), G (Guanine) C (Cytosine) only. But for the cyborgs, it can be anything from A to X. But that has made the problem only five folds more complicated. It’s their ability to synthesize two DNAs from two different cyborgs to create another with all the quality of the parent that gives us the shriek.
We came to know that the relative ordering of the A, B, C, …, X in a cyborg gene is crucial. A cyborg with a gene “ABAAXGF” is quite different from the one with “AABXFGA”. So when they synthesize the genes from two cyborgs, the relative order of these elements in both the parents has to be maintained. To construct a gene by joining the genes of the parents could have been very simple if we could put the structure from the first parent just before the structure of the second parent. But the longer the structure gets, the harder it gets to create a cyborg from that structure. The cyborgs have found a cost effective way of doing this synthesis. Their resultant genes are of the shortest possible length. For example, they could combine “ABAAXGF” and “AABXFGA” to form “AABAAXGFGA”. But that’s only one of the cyborgs that can be created from these genes. This “cost effective synthesis” can be done in many other ways.
We require you to find the shortest length of the gene structure that maintains the relative ordering of the elements in the two parent genes. You are also required to count the number of unique cyborgs that can be created from these two parents. Two cyborgs are different when their gene structures differ in at least one place.
Input
The first line of the input gives you the number of test cases, T (1 ≤ T ≤ 15). Then T test cases follow. Each of the test cases consists of two lines. The first line would give you the gene structure of the first parent, and the second line would give you the structure of the second parent. These structures are represented by strings constructed from the alphabet A to X. You can assume that the length of these strings does not exceed 30 characters.
Output
For each of the test cases, you need to print one line of output. The output for each test case starts with the test case number, followed by the shortest length of the gene structure and the number of unique cyborgs that can be created from the parent cyborgs. You can assume that the number of new cyborgs will always be less than 232. Look at the sample output for the exact format.
Sample Input |
Output for Sample Input |
3 |
Case #1: 10 9 |
Illustration
The first test case is illustrated below:
题意: 给定两个字符串,求出一个新串, 要求新串里面包含两个字符串,求出该串最小长度和在该长度下的总数。
思路:第一步用LCS,求出最长公共子序列,在用两串长度和减去该长度,第二步用了记忆化。从两串末尾开始。如果字符相同,同时去掉该字符,如果不同,则加上第一串去掉字符和第二串去掉字符。
代码:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std; const int N = 35;
int t, lena, lenb, len, vis[N][N][N * 2], dp[N][N][N * 2];
char a[N], b[N], d[N][N]; int dfs(int x, int y, int len) {
if (vis[x][y][len])
return dp[x][y][len];
int &ans = dp[x][y][len];
if (x == 0 || y == 0) {
vis[x][y][len] = 1;
if (x + y == len)
ans = 1;
else
ans = 0;
return ans;
}
if (a[x] == b[y])
ans += dfs(x - 1, y - 1, len - 1);
else
ans += dfs(x - 1, y, len - 1) + dfs(x, y - 1, len - 1);
vis[x][y][len] = 1;
return ans;
} int main() {
scanf("%d%*c", &t);
int tt = 1;
while (t --) {
memset(vis, 0, sizeof(vis));
memset(dp, 0, sizeof(dp));
gets(a + 1); gets(b + 1);
lena = strlen(a + 1); lenb = strlen(b + 1);
for (int i = 1; i <= lena; i ++)
for (int j = 1; j <= lenb; j ++) {
if (a[i] == b[j]) {
d[i][j] = d[i - 1][j - 1] + 1;
}
else {
d[i][j] = max(d[i - 1][j], d[i][j - 1]);
}
}
len = lena + lenb - d[lena][lenb];
printf("Case #%d: %d %d\n", tt ++, len, dfs(lena, lenb, len));
}
return 0;
}
最新文章
- pwnable.kr-random
- .NET初学者推荐课程 asp.net错误代码大全
- DEVMODE 结构体
- STM32F407移植contiki2.6后使用LWIP库实现tcp client
- [jobdu]最小的K个数
- Redhat6.4 配置本地网络的FTP YUM源
- android 添加左右滑屏手势
- poj1584 A Round Peg in a Ground Hole 判断多边形凹凸,点到线的距离【基础计算几何】
- python的try方法中的else和finally的区别
- Nginx使用图片处理模块
- C++string函数之strcpy_s
- MFC:编辑区 Edit 的属性及使用
- Redis 数据类型归纳
- 人类阅读的优越方式打印php数组
- SpringMVC之单/多文件上传
- 根据请求号(request ID)查找正在运行的sql
- javascript 数组函数
- Python网络_TCP/IP简介
- Underscore.js(1.9.1) 封装库
- GreenDao-自定义SQL查询-拼接多个查询条件-AndroidStudio