- 浏览: 316193 次
- 性别:
- 来自: 珠海
文章分类
最新评论
-
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 1524UVa 题号: 10131 Is Bigger Smart ... -
UVA 10201 Adventures in Moving - Part IV
2013-02-01 17:40 1720// [解题方法] // dp[i][j]表示到达第 ... -
UVA 10271 Chopsticks
2013-02-01 11:47 2256// [解题方法] // 将筷子按长度从大到小排序 ... -
UVA 10261 Ferry Loading
2013-01-31 16:34 3167// [题意] // n辆车按顺序安排在一个渡口的左 ... -
UVA 10003 Cutting Sticks
2013-01-31 15:35 1974// [解题方法] // 记忆化搜索(递归,子问题的 ... -
UVA 116 Unidirectional TSP
2013-01-30 09:53 1757// [解题方法] // 记忆化搜索(递归,子问题的 ... -
UVA 10154 Weights and Measures
2013-01-30 09:40 2036// 乌龟塔问题:每个乌龟有力量和重量,求最多能堆多少乌 ... -
UVA 10069 Distinct Subsequences
2013-01-29 16:23 1502// [解题方法] // dp[i][j]表示Z串的 ... -
UVA 10131 Is Bigger Smarter?
2013-01-29 16:01 1874// [解题方法] // 对大象增加编号属性i,以免 ... -
【拓扑+DP】HDU 4109 Instrction Arrangement
2012-03-25 23:34 1435KIDx的解题报告 题目链接:http://acm ... -
【最大不连续子序列和】HDU 2845 Beans
2012-03-08 22:09 3596KIDx的解题报告 题目链接:http://acm.h ... -
Codeforces Beta Round #96 (Div. 2)【完整题解】
2011-12-06 17:03 1474KIDx 的解题报告 题目链接:http://codeforc ... -
Codeforces Beta Round #4 (Div. 2 Only) 【完整题解】
2011-11-08 00:33 1423KIDx 的解题报告 http://codeforces.c ... -
【最长递增子序列O(nlgn)算法】HDU 1025
2011-09-10 15:36 1593http://acm.hdu.edu.cn/showprobl ... -
大连2011ACM网络赛【5道水题总结】……很黄很暴力
2011-09-04 18:04 2586KIDx 的解题报告 http://acm.hdu.ed ... -
【二维分组背包记录路径】暗黑破坏神
2011-08-24 19:48 2036http://openoj.awaysoft.com/Judg ... -
HDU 1087 Super Jumping! Jumping! Jumping!
2011-06-02 18:59 3285http://acm.hdu.edu.cn/showprobl ... -
POJ_3260_The Fewest Coins
2011-05-13 23:18 1212http://poj.org/problem?id=3260 ... -
POJ_3211_Washing Clothes
2011-05-13 23:05 1588http://poj.org/problem?id=3211 ... -
POJ_1742_Coins
2011-05-13 22:33 1030http://poj.org/problem?id=1742 ...
相关推荐
常见的DP题目类型包括但不限于最长公共子序列、背包问题、最短路径、区间调度等。 在动态规划中,我们通常遵循以下步骤: 1. **定义状态**:确定问题的状态,通常是问题的关键属性的组合。 2. **状态转移方程**:找...
动态规划通常用于解决那些可以通过子问题的最优解来构建原问题最优解的问题,例如背包问题、最长公共子序列、最短路径等。 描述中提到的“动态规划DP题解”和“POJ HDU部分动态规划DP题解”,说明这个压缩包包含了...
在编程竞赛中,动态规划常用于解决背包问题、最长公共子序列、最短路径等问题。理解动态规划的状态转移方程和边界条件是掌握这一方法的关键。 这个压缩包中的300+ AC代码提供了丰富的示例,可以帮助学习者深入理解...
经典的DP问题包括最长公共子序列、最短路径问题(如Floyd-Warshall算法)、背包问题等。 8. **并查集**:并查集是一种用于处理集合合并和查询是否属于同一集合的数据结构。在图论中,它可以用来判断两个节点是否...
4. 字符串问题:如最长公共子序列、编辑距离等,它们可以通过构建二维状态数组来求解。 5. 排列组合问题:如组合计数、排列计数等,动态规划能够有效地解决这类问题。 6. 棋盘类问题:如八皇后问题、骑士周游问题...
在ACM竞赛中,动态规划常用于解决如背包问题、最长公共子序列、最短路径等经典问题。 本压缩包中的“lecture_04”可能代表第四次课程,主题为“动态规划(1)_20090309.ppt”,这是一份2009年3月9日的PPT讲座,内容...
在ACM竞赛中,动态规划常用于求解最优化问题,如背包问题、最长公共子序列等。通过将问题分解为子问题,然后存储和利用子问题的解来构建原问题的最优解,动态规划能够有效地避免重复计算。 计算几何(Computational...
其中,确定性问题如斐波那契数列、最长公共子序列等,概率性问题则涉及随机决策过程。 2. **动态规划的五要素** - 状态:定义问题的每一个决策阶段; - 决策:每个状态下的可行操作; - 初始状态:问题的起始...
9.公共子序列(hoj 1227 Common Subsequence) 10.桥接的信号(hoj 1288 Bridging Signals) 算法题 leetcode mysql 1. MySQL 索引使用有哪些注意事项呢? 2. MySQL 遇到过死锁问题吗,你是如何解决的? 3. 日常工作...
在ACM竞赛中,动态规划常用于解决背包问题、最长公共子序列、矩阵链乘法等。学习动态规划需要理解状态转移方程、边界条件以及如何构造状态空间。 二、计算几何 计算几何是研究几何问题与算法的学科,它在ACM竞赛中...
维护一个数组 dp,dp[i] 表示长度为 i 的最长上升子序列的末尾元素的最小值。 2. 遍历原序列,对于每个元素,使用二分查找找到它应该插入 dp 的位置。 ### 搜索 #### 1. Dancing Links - **概念**:一种用于求解...