先看看前aQ?a style="color: rgb(49,52,40); text-decoration: none" >http://www.wutianqi.com/?p=2298
q蝲ȝ录：http://www.wutianqi.com/?p=2403
说到贪心法Q避免不了于DPҎQ所以前面的DP要了解?/p>
贪心法是所做的选择看v来都是当前最佳的Q期望通过所做的局部最优选择来生一个全局最优解?/span>
依然和上一章ȝDP一P我先l出一个最Ҏ入门的例子，来看看神马是贪心Q?是h׃贪心Q这个算法很人性化?/p>
=?)
一个最单的例子Q?/p>
部分背包问题Q?/p>
有N个物品，Wi个物品h值viQ重wiQ现在你有一个可以装W 的包，你可以选择带走每个物品的全部或一部分Q求如何选择可以使背包所装的价值最大？(q个是不是和前面DP中讲?1背包很像Q认真看清楚两者题目的不同Q?
假如有三U物品，背包可装50的物品Q物??0，价?0元；物品2?0，价?00元；物品3?0，价?20元。因此，既然可以选择只装一部分Q我们可以算出每U物品的单位价|物品1是每?元，物品2是美?元，物品3是每?元。按照贪心策略，应该现状物品1Q如果装完物?背包q有I间Q再装物?……
最后的l果是：
而如果按01背包Q则l果是：
有兴的可以拿我?1背包的程序去验证q个l果?/p>
下面是一个部分背包的程序：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <algorithm> using namespace std; typedef struct Thing{ double v; // value double w; // weight }Thing; Thing arr[100]; int n; double W; bool cmp(Thing a, Thing b) { return a.v/a.w > b.v/b.w; } int main() { cout << "输入物品个数: "; cin >> n; cout << "输入背包可蝲重量: "; cin >> W; cout << "输入" << n << "个物品的价值和重量:" << endl; for(int i=0; i<n; ++i) cin >> arr[i].v >> arr[i].w; sort(arr, arr+n, cmp); int k = 0; double value = 0; while(W) { if(W >= arr[k].w) { W -= arr[k].w; value += arr[k].v; } else { value += W * arr[k].v / arr[k].w; W = 0; } ++k; } cout << "最大h值是: " << value << endl; return 0; } |
l果如图Q?/p>
]]>
首先说一下，ACM的入门方法多U多P大部分hq是跟着学校一起参加集训，所以我q里主要是想寚w些准备ACM入门的业余的朋友谈的?/p>
入门书籍Q?/p>
首先推荐一些ACM的书c：
(以下我都会给出在当当|的面Q方便大家直接购乎ͼ以下排名不分先后)
1.《程序设计导引及在线实践?br />http://product.dangdang.com/product.aspx?product_id=20051430&ref=search-1-pub
q是我的W一本入门书Q这本书是配套北大的癄习题Q注意不是POJQ貌似是北大内部试用的Q不q也是对外开攄Q去q好像百炼变化过Q所以[u]不知道这本书q适不适合那个新的癄pȝ[/u]?/p>
2.《算法竞赛入门经典?br />http://product.dangdang.com/product.aspx?product_id=20724029&ref=search-1-pub
q本书没话说Q刘汝佳的白书，l典的算法入门书c。[b]强烈推荐[/b]Q?/p>
3.《算法艺术与信息学竞赛?br />http://product.dangdang.com/product.aspx?product_id=8811386&ref=search-1-pub
刘汝佳的黑书Q难度较深，题目基本来至UvaQ我是看了前面以部分Q后面就没咋看了。。?/p>
4.《算法导论?br />http://product.dangdang.com/product.aspx?product_id=9211884&ref=search-1-pub
l典的书c是不需要解释的?br />q是我曾l上传过的英文版CHM法DQ可以下载了看看Q?br />http://www.cppleyuan.com/viewthread.php?tid=5130&highlight=%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA
我最q也在写法D的读书ȝQ欢q大家探讨：
http://www.wutianqi.com/?p=2403
5.《编E之?br />http://product.dangdang.com/product.aspx?product_id=20170952&ref=search-1-pub
挺有意思的Q不能作Z个算法的全面书籍Q而是作ؓ一本拓宽思维的书c，有兴的要看看?/p>
6.《计机E序设计艺术?br />http://product.dangdang.com/product.aspx?product_id=690222&ref=search-1-pub
有好几卷的，只给ZLq接Q而且|上版本很多Q大家可以自行选择?br />q个q没看，关键是没旉了，准备考研完了p着假期看完?/p>
7.《组合数学?br />http://product.dangdang.com/product.aspx?product_id=8976756&ref=search-0-mix
鸽l原理Q博弈，Ҏ原理QCatalan数等都属于这个范畴的Q徏议看看?/p>
8.《数据结构（C语言版）》严蔚敏
http://product.dangdang.com/product.aspx?product_id=9268172&ref=search-1-pub
数据l构Q这个必d学好啊~~~
9.《数据结构与法分析C++描述Q第三版Q?br />http://product.dangdang.com/product.aspx?product_id=9239535&ref=search-1-pub
有时间可以看看，C++ Template写的Q可以顺便mZtemplate?/p>
以下基本都没看过Q不q貌似很有名Q给Z名和q接Q?br />10.《世界大学生E序设计竞赛QACM/ICPCQ高U教E?W一?E序设计中常用的计算思维方式?br />http://product.dangdang.com/product.aspx?product_id=20645866&ref=search-1-pub
q本我其实买了，但是q没有时间看?/p>
11.《国际大学生E序设计竞赛指南—ACME序设计?br />http://product.dangdang.com/product.aspx?product_id=20450827&ref=search-1-pub
12.《国际大学生E序设计竞赛例题解（三）图论、动态规划算法、综合题专集?br />http://product.dangdang.com/product.aspx?product_id=9352432&ref=search-1-pub
q个好像也有好几册，每一册都是单独讲一个方面的?/p>
13.《挑战编E：E序设计竞赛训练手册?br />http://product.dangdang.com/product.aspx?product_id=20637355&ref=search-1-pub
(作者：Tanky Woo, 个h博客Q?/span>http://www.wutianqi.com QC++/法论坛Q?/span>http://www.cppleyuan.com/ 。{载请注明个h及原文连接，谢谢合作)
入门ҎQ?br />q么多书Q不可能全部都看的，我觉得前10本，也就是我看过的，都还不错Q大家可以看看?br />另外Q我个h推荐ACM可以q样入门(以下用到了上面书c前面的序号)Q（当然Q如果学校有专门培训的，则跟着学校来更好）
1.数据l构是基Q徏议先?号严蔚敏老师的《数据结构》好好看1~2遍，代码都手动敲一敌Ӏ?br />2.再看2?strong>刘汝佳的白书?br />3.d暑假(2010.7~2010.9?Q我曄l我的论?C++奋斗乐园Q?a title="http://www.cppleyuan.com/" style="color: rgb(49,52,40); text-decoration: none" >http://www.cppleyuan.com/)搞过一?strong>ACM专题训练Q训l题全部来至HDOJQ当时我是由易到难，每天选择一个专题，在HDOJ上找3~4题，然后在论坛给出题目，大家可以到HDOJL交，然后贴到论坛供其他朋友参考。板块是Q?a style="color: rgb(49,52,40); text-decoration: none" >http://www.cppleyuan.com/forumdisplay.php?fid=40Q前面都是看书，q里徏议大家开始实战了Q在论坛里一共除?00多题Q大家一定要做！
4.有了一定的基础Q就可以?strong>一边进行深?看书)Q一边做?/strong>了。这个时候神马《算法导论》，《计机E序设计艺术》等{都可以看看?br />5.Cq个阶段Q没啥说的了Q?strong>自由学习~~~
最后说一句：法力Q无与u比，Ƣ迎大家来到ACM的世界！加aQ?/p>
(作者：Tanky Woo, 个h博客Q?a style="color: rgb(49,52,40); text-decoration: none" >http://www.wutianqi.com QC++/法论坛Q?a title="http://www.cppleyuan.com/" style="color: rgb(49,52,40); text-decoration: none" >http://www.cppleyuan.com/ 。{载请注明个h及原文连接，谢谢合作)
]]>
先看看前aQ?a href="http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html">http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
q个案例也比较简单，最长公共子序列(LCS)Q网上的分析非常多，l力啊！
按照上一ȝ所说的Q找状态{ULE：
所以按照所l?a style="color: rgb(49,52,40); text-decoration: none" >方程Q写代码的工作就非常非常单轻松了Q?/p>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
/* Author: Tanky Woo Blog: www.WuTianQi.com About: 《算法导论?5.4 最长公p序列(LCS) */ #include <iostream> using namespace std; char b[20][20]; int c[20][20]; char x[20], y[20]; void LCS() { int m = strlen(x+1); int n = strlen(y+1); for(int i=1; i<=m; ++i) c[i][0] = 0; for(int j=1; j<=n; ++j) c[0][j] = 0; for(int i=1; i<=m; ++i) for(int j=1; j<=n; ++j) { if(x[i] == y[j]) { c[i][j] = c[i-1][j-1] + 1; b[i][j] = '\\'; // 注意q里W一个\\是{UdW，代表\ } else if(c[i-1][j] >= c[i][j-1]) { c[i][j] = c[i-1][j]; b[i][j] = '|'; } else { c[i][j] = c[i][j-1]; b[i][j] = '-'; } } } void printLCS(int i, int j) { if(i == 0 || j == 0) return; if(b[i][j] == '\\') { printLCS(i-1, j-1); cout << x[i] << " "; } else if(b[i][j] == '|') printLCS(i-1, j); else printLCS(i, j-1); } int main() { cout << "Input the array A:\n"; cin >> x+1; cout << "Input the array B:\n"; cin >> y+1; LCS(); printLCS(strlen(x+1), strlen(y+1)); } |
看书上图15-6的结果图Q?/p>
又是一个给力的?自己按照E序把这个图d?
另外,说到LCS,不得不说的是LIS(最长上升子序列)Q也是一个DPQ我曄ȝq：
http://www.wutianqi.com/?p=1850
在我独立博客上的原文Q?a >http://www.wutianqi.com/?p=2505
Ƣ迎大家互相学习Q互相进步！
]]>
先看看前aQ?a href="http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html">http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
q一节可以看?a style="color: rgb(49,52,40); text-decoration: none" >《算法导论》学习ȝ — 16.W?5?动态规?1) 基本入门的补充?/p>
采用动态规划的最优化问题的两个要素：最优子l构?strong>重叠子问?/font>?/font>
先看看最优子l构Q?/p>
在第17ȝӞ装配U调度问题中Q已l设计到了最优子l构Q证明最优子l构问题可以用书上说?#8220;剪脓技?#8221;Q即假设存在更优的解Q来反正最优解矛盾?/p>
再看看重叠子问题Q?/p>
当一个递归法不断的调用同一个问题时Q我们说该最有问题包?#8220;重叠子问?#8221;?/p>
上面q句话不好理解？
看看下面q个比较Q?/p>
递归法Q自而下Q对在递归树中重复出现的每个子问题都要重复解一ơ?/p>
动态规划：自下而上Q对每个只解一ơ?/p>
l合W?6ȝ的三角Ş求g子，可以看得刎ͼ自下而上D每个子问题只求解一ơ?/p>
以上理论性有点强Q我最开始学DP看的是HDOJ的课Ӟ有兴的可以ȝ看?/p>
在那里面Q主要讲C是找状态{ULE，在第16的三角形求g子和W?7的装配U调度例子，那些递归公式都是状态{ULE?/p>
下面q段话好好理解：
——————————————————————–
动态规划的几个概念:
阶段Q据I间序或时间顺序对问题的求解划分阶Dc?span class="Apple-converted-space">
状态：描述事物的性质Q不同事物有不同的性质Q因而用不同的状态来ȝ。对问题的求解状态的描述是分阶段的?span class="Apple-converted-space">
决策Q根据题意要求，Ҏ个阶D|做出的某U选择性操作?span class="Apple-converted-space">
状态{ULE：用数学公式描qC阶段相关的状态间的演变规律?/p>
动态规划是q筹学的一个重要分支，是解军_阶段决策q程最优化的一U方法?/p>
所谓多阶段决策q程Q是所研究的过E划分ؓ若干个相互联pȝ阶段Q在求解ӞҎ一个阶D都要做出决{，前一个决{确定以后，常常会媄响下一个阶D늚决策?/p>
动态规划所依据的是“最优性原?#8221;?span class="Apple-converted-space">
“最优性原?#8221;可陈qCؓQ不论初始状态和W一步决{是什么，余下的决{相对于前一ơ决{所产生的新状态，构成一个最优决{序列?/p>
最优决{序列的子序列，一定是局部最优决{子序列?span class="Apple-converted-space">
包含有非局部最优的决策子序列，一定不是最优决{序列?/p>
动态规划的指导思想是：
在做每一步决{时Q列出各U可能的局部解Q之后依据某U判定条Ӟ舍弃那些肯定不能得到最优解的局部解。这P在每一步都l过{选，以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝Q从搜烦角度看）Q效率会十分高。但它又不同于贪心法。贪心法只能做到局部最优，不能保证全局最优，因ؓ有些问题不符合最优性原理?/font>
——————————————————————–
看见有h说递归是DFSQ而DP是BFSQ感觉有那么一Ҏ思，对于DPQ就是从底层一层层的计，然后在当层中选取最优，逐层最优以xM最优?/p>
其实q个q是多做一些题好?⊙?#8857;)Q大家别认ؓ我是做题控，其实说实在话Q看N遍不如做一题，说白了，法数学本一Ӟ法是数学Q走q高中的Q都知道数学题得多做Q尤其压轴题Q看N遍不如做一遍，q个也是一样做几题q道DP是神马东东了Q?/p>
在我独立博客上的原文Q?a >http://www.wutianqi.com/?p=2500
Ƣ迎大家互相学习Q互相进步！
]]>
先看看前aQ?a href="http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html">http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
原来打算把算法导论在7月䆾前搞定，现在已经q去一个多月了Q才只看到第15章，后面也只零散看了一些，不知道假期前能否看完。。。够呛啊Q马上要期末考试了，上学期GPA不到2Q被学位警告了，虽说以后不学q个专业了，但v码成l单上也不能有挂U是吧。。。要是^时一点不看，考前靠春哥，曑֓Q关公哥都不行啊。。。这q度Q郁P
力吧！
Zq是说两句话Q?/p>
1.有些书上分析的相当好了，我不惛_画蛇添的hQ所以有的地Ҏ会适当省略Q当然也不是说我ȝ的地方就是书上讲的不好的地方Q只是没人有一套自q理解方式Q我用自q话去ȝ了，当时也就是最适合我的知识Q所以，大家多写一些算法ȝQ你会体会到好处的！
2.而且我这个的性质是ȝQ不是对一个算法的具体讲解Q所以不先看书，大家应该M懂的Q就比如下面Q题目我没有脓出来Q大家不看数Q肯定就M懂，我的目的是大家看完书后，谢谢ȝQ或者看看别人写的ȝQ说不定可以发现自己哪些地方理解错了Q哪些地方不理解Q或是哪些地方值得探讨?/p>
先看看前aQ?a title="http://www.wutianqi.com/?p=2298" style="color: rgb(49,52,40); text-decoration: none" >http://www.wutianqi.com/?p=2298
q一ơ主要是分析15.1节的例子—装配U调度问题?/p>
题目有点长，首先得把题目L?/p>
q个例子书上׃6面纸的篇q来详细分析Q由此可见其重要性?/p>
谈到DP,不得不说的就是暴力法Q大安知道Q如果用暴力解决cM问题Q一般时间复杂度都是非常非常的高Q这个时候救世主DP出来了QDP以避免了许多重复的计，而大大降低了旉复杂度?/p>
按照书上的四个步骤，我在q里提取一些重点，q是把P194~196q四步完整步骤看书上的分析。只有慢慢品呻I你才会发现《算法导论》的?/p>
步骤一Q?/p>
分析问题Q比如一个底盘要到达S[1][j]Q则有两U情况，W一U是从S[1][j-1]到S[1][j]Q第二种是从S[2][j-1]到S[1][j]。找两者所花时间的最，则就是S[1][j]所需旉的最?/p>
q就是有局部最优解求全局最优解。也是_一个问题的最优解包含了子问题的一个最优解。我们称q个性质为最优子l构。这是是否可以应用DP的标志之一?/p>
步骤?/strong>Q?/p>
扑ևq个递归关系Q由步骤一可以得到q个递归关系Q?/p>
步骤?/strong>Q?/p>
因ؓ递归的关p，一般L可以转换为非递归的算法?/p>
由已知量f1[1], f2[1]逐步推出未知量，推啊推，推啊推，最后就推到l果了~~~~ 步骤?/strong>Q?/p>
再由已知l果q回求\径?/p>
q一节最l力的就是这个例子以及相应的?/strong>Q?/p>
拿vW，用书上给出的例子Q分析这个图Q?/p>
以下是代码： 最后还是要感叹一下，《算法导论》讲的真是棒极了Q希望大家能静下心把q一章节好好看看?br /> 在我独立博客上的原文Q?a >http://www.wutianqi.com/?p=2496 Ƣ迎大家互相学习Q互相进步！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*
Author: Tanky Woo
Blog: www.WuTianQi.com
About: 《算法导论?5.1 装配U调?
*/
#include <iostream>
using namespace std;
int n; // 一个装配线上有n个装配站
int e1, e2; // q入装配U?,2需要的旉
int x1, x2; // d装配U?,2需要的旉
int t[3][100]; // t[1][j]表示底盘从S[1][j]Ud到S[2][j+1]所需旉,同理t[2][j]
int a[3][100]; // a[1][j]表示在装配站S[1][j]所需旉
int f1[100], f2[100]; // f1[j], f2[j]分别表示在第一/W二条装配线上第j个装配站的最优解
int ln1[100], ln2[100];// ln1[j]记录W一条装配线?最优解时第j个装配站的前一个装配站是第一条线q是W二条线?/span>
int f, ln; // 最优解?f代表最花Ҏ_ln表示最后出来时是从装配U?q是装配U?
void DP()
{
f1[1] = e1 + a[1][1];
f2[1] = e2 + a[2][1];
for(int j=2; j<=n; ++j)
{
// 处理W一条装配线的最优子l构
if(f1[j-1] + a[1][j] <= f2[j-1] + t[2][j-1] + a[1][j])
{
f1[j] = f1[j-1] + a[1][j];
ln1[j] = 1;
}
else
{
f1[j] = f2[j-1] + t[2][j-1] + a[1][j];
ln1[j] = 2;
}
// 处理W二条装配线的最优子l构
if(f2[j-1] + a[2][j] <= f1[j-1] + t[1][j-1] + a[2][j])
{
f2[j] = f2[j-1] + a[2][j];
ln2[j] = 2;
}
else
{
f2[j] = f1[j-1] + t[1][j-1] + a[2][j];
ln2[j] = 1;
}
}
if(f1[n] + x1 <= f2[n] + x2)
{
f = f1[n] + x1;
ln = 1;
}
else
{
f = f2[n] + x2;
ln = 2;
}
}
void PrintStation()
{
int i= ln;
cout << "line " << i << ", station " << n << endl;
for(int j=n; j>=2; --j)
{
if(i == 1)
i = ln1[j];
else
i = ln2[j];
cout << "line " << i << ", station " << j-1 << endl;
}
}
int main()
{
//freopen("input.txt", "r", stdin);
cout << "输入装配站的个数: ";
cin >> n;
cout << "输入q入装配U?Q?所需的时间e1, e2 :";
cin >> e1 >> e2;
cout << "输入d装配U?, 2所需的时间x1, x2: ";
cin >> x1 >> x2;
cout << "输入装配U?上各站加工所需旉a[1][j]: ";
for(int i=1; i<=n; ++i)
cin >> a[1][i];
cout << "输入装配U?上各站加工所需旉a[2][j]: ";
for(int i=1; i<=n; ++i)
cin >> a[2][i];
cout << "输入装配U?上的站到装配U?上的站所需旉t[1][j]: ";
//注意q里是i<nQ不是i<=n
for(int i=1; i<n; ++i)
cin >> t[1][i];
cout << "输入装配U?上的站到装配U?上的站所需旉t[2][j]: ";
for(int i=1; i<n; ++i)
cin >> t[2][i];
DP();
cout << "最快需要时? " << f << endl;
cout << "路线? " << endl;
PrintStation();
cout << endl;
}
]]>
W十四章我想攑֜后面再看Q先搁下。希望大家ȝ的一些文章也能向我推荐下Q大家互相学习?/p>
首先Q还是徏议看看前aQ?a href="http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html">http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
其次Q阿门，感谢老天送给了我们这么一本圣l，看了q一章，再次感受C《算法导论》分析问题的_辟Q强悍的力。Orz, Orz,各种Orz?/p>
q一章讲的是动态规划，学算法的朋友Q尤其是搞ACM的，对这个策略一定非常熟悉，所以这个算法网上的分析讲解教程也是铺天盖地Q大家可以多搜几学习学习?/p>
动态规?/strong>(Dynamic ProgrammingQ简UDP)是通过l合子问题的解来解决问题的?/p>
注意q里的programming不是指编E，而是指一U?strong>规划
因ؓDP用的太广泛了Qƈ且书上也׃很大的篇q来讲这一章，所以我也准备把q一章分几篇来ȝQƈ且我不按照书上的序来ȝQ也不会全部用书上的例子?/p>
q一章首先给Z些基的概念，然后l出一个最基础入门的DP问题Q三角Ş求值问题?/p>
DP适用于子问题不是独立的情况，q样如果用分LQ也会作许多重复的工作，而DP只对子问题求解一ơ，其l果保存在一张表中，从而避免了每次遇到各个子问题时重新计算的情c?/span>
比较分治法于动态规划的区别Q?/p>
分治?/strong>Q将问题划分Z些独立的子问题，递归的求解各子问题，然后合ƈ子问题的解而得到原问题的解?/p>
eg.MERGE-SORT(A, p, r)
1 if p < r
2 then q ← |(p + r)/2|
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 MERGE(A, p, q, r)
动态规?/strong>Q?span style="color: rgb(0,0,255)">适用于子问题不是独立的情况，也就是各子问题包?strong>公共的子子问?/strong>Q鉴于会重复的求解各子问题，DPҎ个问
?strong>只求解一?/strong>Q将?strong>保存在一张表中，从而避免重复计?/span>
DP法的设计可以分?strong>四个步骤Q?/p>
①.描述最优解的结构?/span>
②.递归定义最优解的倹{?/span>
③.按自底而上的方式计最优解的倹{?/span>
④.p出的结果创造一个最优解?/span>
下面来看看三角Ş求D个问题：
一个由N行数字组成的三角形，如图所以，设计一个算法，计算Z角Ş的由至底的一条\径，使该路径l过的数字d最大?/p>
q是在我见过的DP题目中，是最单的了，我相信就没有学qDP的也会?/p>
上图{化一下：
假设上图用map[][]数组保存?/p>
令f[i][j]表示从顶?1, 1)到顶?i, j)的最大倹{?/p>
则可以得到状态{ULE：
f[i][j] = max(f[i+1][j], f[i+1][j+1]) + map[i][j]
此题既适合自顶而下的方法做Q也适合自底而上的方法，
当用自顶而下的方法做Ӟ最后要在在最后一列数中找出最大|
而用自底而上的方法做Ӟf[1][1]即ؓ最大倹{?/p>
所以我们将?Ҏ状态{ULE可以得到图3Q?/p>
最大值是30.
很简单的DP题，代码如下Q?/p>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
/* Author: Tanky Woo Blog: www.WuTianQi.com Description: 动态规划之三角形求值问? */ #include <iostream> using namespace std; int map[6][6] = { {0, 0, 0, 0, 0, 0}, {0, 7, 0, 0, 0, 0}, {0, 3, 8, 0, 0, 0}, {0, 8, 1, 0, 0, 0}, {0, 2, 7, 4, 4, 0}, {0, 4, 5, 2, 6, 5} }; int f[6][6]; int _max(int a, int b) { if(a >= b) return a; return b; } int main() { memset(f, 0, sizeof(f)); for(int i=0; i<6; ++i) f[5][i] = map[5][i]; for(int i=4; i>=1; --i) for(int j=1; j<=i; ++j) f[i][j] = _max(f[i+1][j], f[i+1][j+1]) + map[i][j]; for(int i=1; i<=5; ++i) { for(int j=1; j<=5; ++j) { cout.width(2); cout << f[i][j] << " "; } cout << endl; } cout << f[1][1] << endl; } |
l果如图Q?/p>
下一会装配线的调度?br />
在我独立博客上的原文Q?a >http://www.wutianqi.com/?p=2484
Ƣ迎大家互相学习Q互相进步！
]]>
]]>
q一是关于U黑树的l点删除?/p>
依然和上一的插入一P先用CBST的删除结点函敎ͼ然后做相应的调整?/p>
不过Q这里的调整思\颇ؓ新颖?/p>
q是来看看略微改变后的删除结点函敎ͼ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | Node* RBTreeDelete(RBTree T, Node *z) { Node *x, *y; // z是要删除的节?而y是要替换z的节?/span> if(z->lchild == NULL || z->rchild == NULL) y = z; // 当要删除的z臛_有一个子树，则y=zQ?/span> else y = RBTreeSuccessor(z); // y是z的后l?/span> if(y->lchild != NULL) x = y->lchild; else x = y->rchild; // 无条件执行p[x] = p[y] x->parent = y->parent; if(y->parent == NULL) T = x; else if(y == y->parent->lchild) y->parent->lchild = x; else y->parent->rchild = x; if(y != z) z->key = y->key; if(y->color == BLACK) RBDeleteFixup(T, x); return y; } |
注意代码倒数W二和第三行Q只有当后l点y的颜色是黑色Ӟ才做调整?/p>
由此Q引导出几个问题Q?/p>
1.问：考虑Z当y的颜色是黑色Ӟ才调_当y的颜色是U黑Ӟ会不会破坏性质4Q?/span>
{：q里我一开始纠l了Q后来反复看了几ơBST的删除，再算想通。在BST中，删除l点zQƈ不是真的把zl移除了Q其实删除的不是zQ而是yQ因为z始终没有动过Q只是把y删除了，然后把y的key赋值给z的key。所以，在红黑树中，z的颜色没有变Q依然符合红黑性质。（q里我先开始理解ؓy->color也要赋值给z->colorQ汗。。。）
2.问：考虑y为黑色时Q破坏了哪几条红黑性质Q?/p>
{：当y是根Ӟ且y的一个孩子是U色Q若此时q个孩子成ؓ根结炏V——?gt;破坏了性质2
当x和p[y]都是U色时?nbsp; ——?gt;破坏了性质4
包含y的\径中Q黑高度都减了?nbsp; ——?gt;破坏了性质5
解决ҎQ?/p>
上一我解释q，性质五涉及到了整|Q难以控制?/p>
因此x的颜色增加一重黑Ԍ那么?
?x原先颜色为RED时—?>x包含RED和BLACK两颜?/span>
?x原先颜色是BLACK时?#8211;>x包含BLACK, BLACK两颜艌Ӏ?/span>
此时性质5解决Q但是又破坏了性质1.
接下来就是恢复性质1Q?Q?了?/p>
额外的一重黑色一直沿树向上移Q直到x是根或者是U色l点?/span>
看看具体的实C码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | void RBDeleteFixup(RBTree &T, Node *x) { while(x != T && x->color == BLACK) { if(x == x->parent->lchild) { Node *w = x->parent->rchild; ///////////// Case 1 ///////////// if(w->color == RED) { w->color = BLACK; x->parent->color = RED; LeftRotate(T, x->parent); w = x->parent->rchild; } ///////////// Case 2 ///////////// if(w->lchild->color == BLACK && w->rchild->color == BLACK) { w->color = RED; x = x->parent; } else { ///////////// Case 3 ///////////// if(w->rchild->color == BLACK) { w->lchild->color = BLACK; w->color = RED; RightRotate(T, w); w = x->parent->rchild; } ///////////// Case 4 ///////////// w->color = x->parent->color; x->parent->color = BLACK; w->rchild->color = BLACK; LeftRotate(T, x->parent); x = T; } } else { Node *w = x->parent->lchild; if(w->color == RED) { w->color = BLACK; x->parent->color = RED; RightRotate(T, x->parent); w = x->parent->lchild; } if(w->lchild->color == BLACK && w->rchild->color == BLACK) { w->color = RED; x = x->parent; } else { if(w->lchild->color == BLACK) { w->rchild->color = BLACK; w->color = RED; LeftRotate(T, w); w = x->parent->lchild; } w->color = x->parent->color; x->parent->color = BLACK; w->lchild->color = BLACK; RightRotate(T, x->parent); x = T; } } } x->color = BLACK; } |
对于删除的调_共八U情?左右对称各四U?Q这里在书上P175面讲的很详细Q所以我也就不再d了，大家可以自己拿vW在草稿U怸M
在我独立博客上的原文Qhttp://www.wutianqi.com/?p=2449
Ƣ迎大家互相讨论Q一赯步！
]]>
先看看前aQ?a href="http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html">http://www.shnenglu.com/tanky-woo/archive/2011/04/09/143794.html
插入l点用到了上一ơBST的插入函?做了一Ҏ?Qƈ且在此基上增加了保持U黑性质的调整函数?/p>
q是先看看插入函敎ͼ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
void RBTreeInsert(RBTree &T, int k) { //T->parent->color = BLACK; Node *y = NULL; Node *x = T; Node *z = new Node; z->key = k; z->lchild = z->parent = z->rchild = NULL; while(x != NULL) { y = x; if(k < x->key) x = x->lchild; else x = x->rchild; } z->parent = y; if(y == NULL) { T = z; T->parent = NULL; T->parent->color = BLACK; } else if(k < y->key) y->lchild = z; else y->rchild = z; z->lchild = NULL; z->rchild = NULL; z->color = RED; RBInsertFixup(T, z); } |
和上一ơ的BST基本没区别，只是d了对新加l点z的颜色和子节点的处理?/p>
q里把z的颜色设|ؓU色Q然后进行处理?/p>
?/strong>Q考虑Z把z的颜色设|ؓU色Q?/p>
{?/strong>Q个为如果设|ؓ黑色Q则破坏了性质五，而性质五关于黑高度的问题，涉及C整棵树，全局性难以把握，所以这里设|ؓU色Q虽然破坏了性质4Q然是相对破坏性质5来说Q更Ҏ恢复U黑性质。大家如果有不同的想法，也可以留a谈谈?/span>
接下来，是Ҏ|的调整了?/p>
{：考虑插入zl点后，破坏的哪几条U黑性质Q?/p>
{：破坏了性质2和性质4.
5条红黑性质要熟讎ͼ我这里再贴出来：
1. 每个l点或是U色Q或是是黑色?br>2. 根结Ҏ黑的?br>3. 所有的叶结?NULL)是黑色的。（NULL被视Z个哨늻点，所有应该指向NULL的指针，都看成指向了NULLl点。）
4. 如果一个结ҎU色的，则它的两个儿子节炚w是黑色的?br>5. Ҏ个结点，从该l点到其子孙l点的所有\径上包含相同数目的黑l点?/p>
所以我们要做的是恢复性质2和性质4.
先来看看具体实现的代?q里只脓出部分代?Q?/p>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
void RBInsertFixup(RBTree &T, Node *z) { while(z->parent->color == RED) { if(z->parent == z->parent->parent->lchild) { Node *y = z->parent->parent->rchild; //////////// Case1 ////////////// if(y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { ////////////// Case 2 ////////////// if(z == z->parent->rchild) { z = z->parent; LeftRotate(T, z); } ////////////// Case 3 ////////////// z->parent->color = BLACK; z->parent->parent->color = RED; RightRotate(T, z->parent->parent); } } else { /////////////////////// } } T->color = BLACK; } |
分三U情况，在代码中已用Case 1, Case 2, Case 3标记出?/p>
大致说下判断情况Q?/p>
1.首先让一个指针y指向z?span style="COLOR: rgb(0,0,255)">叔父l点
(z是要删除的结??/p>2.如果y的颜色是U色QCase 1。则使z的父亲结点和叔父l点的颜色改为黑Qz的祖父结炚w色改为红。然后让z转移到z的祖父结炏V?/p>
3.当y的颜色是黑色Ӟ
?首先判断z是否是其父亲l点的右儿子Q若是，?span style="COLOR: rgb(0,0,255)">调整为左儿子(用旋??/p>
?其次使z的父亲结炚w色ؓ黑，z的祖父结炚w色ؓU，q以z的祖父结?/span>ux?/p>
具体我还是在草稿U怸d。。?可怜买不v数码相机Q只能用手机拍了。。? Q弱q问一句，看见|上有很多朋友做的一些代码讲解图很给力，不知道大家有什么Y件吗Q求推荐。。。） 以下是插入的完整代码Q?/p>
下一是关于U黑树的删除?br>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
void RBInsertFixup(RBTree &T, Node *z)
{
while(z->parent->color == RED)
{
if(z->parent == z->parent->parent->lchild)
{
Node *y = z->parent->parent->rchild;
//////////// Case1 //////////////
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
////////////// Case 2 //////////////
if(z == z->parent->rchild)
{
z = z->parent;
LeftRotate(T, z);
}
////////////// Case 3 //////////////
z->parent->color = BLACK;
z->parent->parent->color = RED;
RightRotate(T, z->parent->parent);
}
}
else
{
Node *y = z->parent->parent->lchild;
if(y->color == RED)
{
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent;
}
else
{
if(z == z->parent->lchild)
{
z = z->parent;
RightRotate(T, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
LeftRotate(T, z->parent->parent);
}
}
}
T->color = BLACK;
}
void RBTreeInsert(RBTree &T, int k)
{
//T->parent->color = BLACK;
Node *y = NULL;
Node *x = T;
Node *z = new Node;
z->key = k;
z->lchild = z->parent = z->rchild = NULL;
while(x != NULL)
{
y = x;
if(k < x->key)
x = x->lchild;
else
x = x->rchild;
}
z->parent = y;
if(y == NULL)
{
T = z;
T->parent = NULL;
T->parent->color = BLACK;
}
else
if(k < y->key)
y->lchild = z;
else
y->rchild = z;
z->lchild = NULL;
z->rchild = NULL;
z->color = RED;
RBInsertFixup(T, z);
}
]]>