- 浏览: 308739 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
xialluyouyue:
Ubuntu下搭建nodejs+express+mongodb环境简单教程 -
k317544294:
Good 陈迪峰
(开源游戏) DOTA音效版 俄罗斯方块 -
基德KID.1412:
su1216 写道竖线代表或者,不代表替换
对哦~ 谢谢你的提 ...
正则表达式中特殊字符的用法(收藏) -
su1216:
竖线代表或者,不代表替换
正则表达式中特殊字符的用法(收藏) -
qiqijianglu:
基德KID.1412 写道qiqijianglu 写道基德KI ...
【高斯消元 求期望】HDU 4418 Time travel
KIDx的解题报告
第一题(比较简单,不详细解):
HDU 1159 Common Subsequence
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1159
题意:求两个串的最长公共子序列
代码中的dp[i][j]表示0到i-1跟0到j-1的最长公共子序列
#include <iostream> using namespace std; #define M 5005 int dp[M][M]; char a[M], b[M]; int main() { int i, j, la, lb; while (~scanf ("%s%s", a, b)) { la = strlen (a), lb = strlen (b); for (i = 0; i < la; i++) //边界初始化 dp[i][0] = 0; for (j = 0; j < lb; j++) dp[0][j] = 0; for (i = 1; i <= la; i++) { for (j = 1; j <= lb; j++) { //状态转移 if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max (dp[i-1][j], dp[i][j-1]); } } printf ("%d\n", dp[la][lb]); } return 0; }
第二题: HDU 1080 Human Gene Functions 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1080
题意:两个字符串,每个字符串中都可以插入'-',保证最后两串的长度相等,之后让两串对齐,两串相同位置的字母组成的字符匹配有一个值,问这些值的和最大是多少,是第一题的变形 下图为字符匹配所得价值的表 dp[i][j]表示0到i-1跟0到j-1配对的最大价值 状态转移: ①dp[i][j]由dp[i-1][j]转移过来,代价是a[i-1]跟'-'匹配 ②由dp[i][j-1]转移过来,代价是b[j-1]跟'-'匹配 ③由dp[i-1][j-1]转移过来,代价是a[i-1]跟b[j-1]匹配
第三题:#include <iostream>
#include <algorithm>
using namespace std;
#define inf 0x3fffffff
#define M 105
int dp[M][M], v[20][20] = {0};
char a[M], b[M];
int main()
{
v[0][0] = v[2][2] = v[6][6] = v[19][19] = 5;
v[0][2] = v[2][0] = -1;
v[0][6] = v[6][0] = -2;
v[0][19] = v[19][0] = -1;
v[2][6] = v[6][2] = -3;
v[2][19] = v[19][2] = -2;
v[6][19] = v[19][6] = -2;
v[7][0] = -3; //7表示'-',0,2,6,19分别表示A,C,G,T
v[7][2] = -4;
v[7][6] = -2;
v[7][19] = -1;
int i, j, la, lb, t;
scanf ("%d", &t);
while (t--)
{
scanf ("%d%s%d%s", &la, a, &lb, b);
for (i = 0; i <= la; i++)
for (j = 0; j <= lb; j++)
dp[i][j] = -inf;
dp[0][0] = 0;
for (i = 1; i <= la; i++) //一系列的边界初始化
dp[i][0] = dp[i-1][0] + v[7][a[i-1]-'A'];
for (j = 1; j <= lb; j++)
dp[0][j] = dp[0][j-1] + v[7][b[j-1]-'A'];
for (i = 1; i <= la; i++)
{
for (j = 1; j <= lb; j++)
{
//状态转移方程
dp[i][j] = max (dp[i][j],
max (dp[i-1][j-1]+v[a[i-1]-'A'][b[j-1]-'A'],
max (dp[i][j-1]+v[7][b[j-1]-'A'],
dp[i-1][j]+v[7][a[i-1]-'A'])));
}
}
printf ("%d\n", dp[la][lb]);
}
return 0;
}
HDU 1503 Advanced Fruits 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1503 题意: 给你两个单词,然后你要把两个单词拼接成一个新单词,使得新单词的子序列中包含两个单词,并且要使这个新单词最短 基本思路: 求最长公共子序列,令这个序列只输出一次就可以使新单词最短 记录路径: 增加二维数组road记录状态转移路径 road[i][j] = 0 表示road[i][j]由road[i-1][j-1]转移过来,即a[i-1]与b[j-1]属于最长公共子序列中的元素,扫描路径时将hash[i-1]赋值为j-1表示a串的i-1匹配b串的j-1【其中hash初始时全为-1】 road[i][j] = 1 表示road[i][j]由road[i-1][j]转移过来 road[i][j] = 2 表示road[i][j]由road[i][j-1]转移过来 输出答案: 先设置start变量【表示b串的当前位置】,扫描a串 ①当对于a[i]有hash[i]==-1,说明a[i]不是最长公共子序列中的元素,直接输出并且continue; ②否则b串输出从start到hash[i]的值,因为a[i]跟b[hash[i]]匹配嘛,所以输出b[hash[i]]就不用输出a[i]勒,然后start变为hash[i] + 1;
#include <iostream> using namespace std; #define M 105 int dp[M][M], road[M][M], hash[M]; char a[M], b[M]; int main() { int i, j, la, lb; while (~scanf ("%s%s", a, b)) { la = strlen (a), lb = strlen (b); for (i = 0; i < la; i++) dp[i][0] = 0; for (j = 0; j < lb; j++) dp[0][j] = 0; memset (road, -1, sizeof(road)); for (i = 1; i <= la; i++) { for (j = 1; j <= lb; j++) { if (a[i-1] == b[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; road[i][j] = 0; } else { if (dp[i-1][j] > dp[i][j-1]) dp[i][j] = dp[i-1][j], road[i][j] = 1; else dp[i][j] = dp[i][j-1], road[i][j] = 2; } } } int k = 0; memset (hash, -1, sizeof(hash)); i = la, j = lb; while (road[i][j] != -1) //扫描最长公共序列路径 { if (road[i][j] == 0) { i--, j--; hash[i] = j; } if (road[i][j] == 2) j--; if (road[i][j] == 1) i--; } int start = 0; //b串的还没打印的第一个字母的位置 for (i = 0; i < la; i++) { if (hash[i] == -1) //不属于最长公共子序列的元素 { printf ("%c", a[i]); continue; } //a[i]与b[hash[i]]匹配,属于最长公共子序列 for (j = start; j <= hash[i]; j++) printf ("%c", b[j]); start = hash[i] + 1; } for (j = start; j < lb; j++) printf ("%c", b[j]); printf ("\n"); } return 0; }
发表评论
-
《挑战编程》第11章-动态规划
2013-02-02 12:46 1468UVa 题号: 10131 Is Bigger Smart ... -
UVA 10201 Adventures in Moving - Part IV
2013-02-01 17:40 1660// [解题方法] // dp[i][j]表示到达第 ... -
UVA 10271 Chopsticks
2013-02-01 11:47 2199// [解题方法] // 将筷子按长度从大到小排序 ... -
UVA 10261 Ferry Loading
2013-01-31 16:34 3094// [题意] // n辆车按顺序安排在一个渡口的左 ... -
UVA 10003 Cutting Sticks
2013-01-31 15:35 1914// [解题方法] // 记忆化搜索(递归,子问题的 ... -
UVA 116 Unidirectional TSP
2013-01-30 09:53 1652// [解题方法] // 记忆化搜索(递归,子问题的 ... -
UVA 10154 Weights and Measures
2013-01-30 09:40 1959// 乌龟塔问题:每个乌龟有力量和重量,求最多能堆多少乌 ... -
UVA 10069 Distinct Subsequences
2013-01-29 16:23 1422// [解题方法] // dp[i][j]表示Z串的 ... -
UVA 10131 Is Bigger Smarter?
2013-01-29 16:01 1812// [解题方法] // 对大象增加编号属性i,以免 ... -
【拓扑+DP】HDU 4109 Instrction Arrangement
2012-03-25 23:34 1376KIDx的解题报告 题目链接:http://acm ... -
【最大不连续子序列和】HDU 2845 Beans
2012-03-08 22:09 3565KIDx的解题报告 题目链接:http://acm.h ... -
Codeforces Beta Round #96 (Div. 2)【完整题解】
2011-12-06 17:03 1445KIDx 的解题报告 题目链接:http://codeforc ... -
Codeforces Beta Round #4 (Div. 2 Only) 【完整题解】
2011-11-08 00:33 1366KIDx 的解题报告 http://codeforces.c ... -
【最长递增子序列O(nlgn)算法】HDU 1025
2011-09-10 15:36 1558http://acm.hdu.edu.cn/showprobl ... -
大连2011ACM网络赛【5道水题总结】……很黄很暴力
2011-09-04 18:04 2548KIDx 的解题报告 http://acm.hdu.ed ... -
【二维分组背包记录路径】暗黑破坏神
2011-08-24 19:48 1995http://openoj.awaysoft.com/Judg ... -
HDU 1087 Super Jumping! Jumping! Jumping!
2011-06-02 18:59 3249http://acm.hdu.edu.cn/showprobl ... -
POJ_3260_The Fewest Coins
2011-05-13 23:18 1182http://poj.org/problem?id=3260 ... -
POJ_3211_Washing Clothes
2011-05-13 23:05 1548http://poj.org/problem?id=3211 ... -
POJ_1742_Coins
2011-05-13 22:33 988http://poj.org/problem?id=1742 ...
相关推荐
HDU的一题........HDU DP动态规
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...
动态规划DP题解 POJ HDU部分动态规划DP题解
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
hdu 1005.比较简单的一道题,有兴趣的可以看看。
lazycal的集训队报告:初探数位DP 以HDU 2089,HDU 3652, URAL 1057等题目为例,介绍了数位DP的算法
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU ACM 2005第几天 C++ http://acm.hdu.edu.cn/listproblem.php?vol=11 2005题 第几天?
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
自己做的HDU ACM已经AC的题目
ACM HDU题目分类,我自己总结的大概只有十来个吧