C++博客-zhangzm

程序员面试100题_01 把二元查找树转变成排序的双向链表

bluedream — Tue, 31 May 2011 09:12:00 GMT

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

/ \

6 14

/ \ / \

4 8 12 16

转换成双向链表

4=6=8=10=12=14=16。

首先我们定义的二元查找树节点的数据结构如下：

struct BTNode{
int value;
BTNode *left;
BTNode *right;
};

typedef BTNode BTree;

  1 #include <iostream>
  2 #include <cassert>
  3 #include <stack>
  4 using namespace std;
  5
  6 struct BTNode{
  7     int value;
  8     BTNode *left;
  9     BTNode *right;
10 };
11 typedef BTNode BTree;
12
13 void DestoryLink(BTree *T){
14     BTree *tmp;
15     while(T){
16         tmp=T;
17         T=T->right;
18         delete tmp;
19     }
20 }
21 void PrintTree(BTree *T){
22     if(!T)return;
23     PrintTree(T->left);
24     cout<<T->value<<"  ";
25     PrintTree(T->right);
26 }
27
28
29
30 void Insert(BTree *T,BTNode *node){
31     if(!T)return;
32     BTNode *tmp=T,*pre;
33     while(tmp){
34         if(tmp->value > node->value){
35             pre=tmp;
36             tmp=tmp->left;
37         }else if(tmp->value < node->value){
38             pre=tmp;
39             tmp=tmp->right;
40         }else{
41             cout<<"must be unique key"<<endl;
42             return ;
43         }
44     }
45     if(pre->value > node->value){
46         pre->left=node;
47     }else{
48         pre->right=node;
49     }
50 }
51
52 int BuildBTree(BTree *&T,int array[],int num){
53     assert(num>0);
54
55     T=new BTNode;
56     T->left=T->right=NULL;
57     T->value=array[0];
58
59     BTNode *tmp=NULL;
60
61     for(int i=1;i<num;i++){
62         tmp=new BTNode;
63         tmp->left=tmp->right=NULL;
64         tmp->value=array[i];
65         Insert(T,tmp);
66         //cout<
67     }
68     cout<<endl;
69     //PrintTree(T);
70     return 1;
71 }
72
73 int BTreeToDoubleLinkList(BTree *&T,BTNode *&Head){
74     if(!T)return 0;
75
76
77     BTNode *pre,*next,*tmp,*connect;
78     pre=next=NULL;
79     Head=NULL;
80     //return 1;
81     stack<BTNode*> st;
82     st.push(T);
83     tmp=T;
84     int i=0;
86     while(!st.empty()){
87
88         tmp=st.top();
89         while(tmp->left){//一直向左边查找；
90             st.push(tmp->left);
91
92             tmp=tmp->left;
93         }
94
95         if(NULL == Head)Head=tmp;//记录头结点；
96         tmp=st.top();
97         st.pop();
98
99         if(NULL == pre){//记录前驱；
100             pre=tmp;
101         }else{
102             //进行链接；
103             pre->right=tmp;
104             tmp->left=pre;
105             pre=tmp;
106
107         }
108
109         if(tmp->right){
110             tmp=tmp->right;
111             st.push(tmp);
112         }else{
113             //当前元素出栈；
114             tmp=st.top();
115             st.pop();
116             while(!tmp->right){
117                 //右节点为空，进行链接；
118                 pre->right=tmp;
119                tmp->left=pre;//
120                pre=tmp;
121
122                if(st.empty())break;
123                tmp=st.top();
124                st.pop();
125
126             }
127
128             if(tmp->right){
129                 //右节点不为空，进行链接，入栈；
130                 pre->right=tmp;
131                 tmp->left=pre;
132                pre=tmp;
133                st.push(tmp->right);
134             }
135
136
137             //tmp=tmp->right;
138         }
139     }
140 }
141
142
143 int main(){
144
145     //int array[]={10,6,11,4,9,13,8,12,16,7,15,14};
146     int array[]={14,13,15,7,16,10,20,9,12,19,18} ;
147     int num=sizeof(array)/sizeof(int);
148
149     BTree *T=NULL;
150     BTNode *Head=NULL;
151     BuildBTree(T,array,num);
152
153     BTreeToDoubleLinkList(T,Head);
154
155     BTNode *tmp=Head,*pre;
156
157     cout<<" \n in main  print list"<<endl;
158
159     while(tmp){
160         cout<<tmp->value<<" ";
161         pre=tmp;
162         tmp=tmp->right;
163     }
164     cout<<" \nfrom tail to head"<<endl;
165     while(pre){
166         cout<<pre->value<<" ";
167         pre=pre->left;
168     }
169
170     cout<<endl;
171     DestoryLink(Head);
172
173     system("pause");
174     return 0;
175 }
176
177
178
179
180
181
182
183
184
185
186
187
188
189

bluedream 2011-05-31 17:12 发表评论

转 POJ 计算几何入门题目推荐

bluedream — Thu, 17 Jun 2010 07:58:00 GMT

计算几何题的特点与做题要领：
1.大部分不会很难，少部分题目思路很巧妙
2.做计算几何题目，模板很重要，模板必须高度可靠。
3.要注意代码的组织，因为计算几何的题目很容易上两百行代码，里面大部分是模板。如果代码一片混乱，那么会严重影响做题正确率。
4.注意精度控制。
5.能用整数的地方尽量用整数，要想到扩大数据的方法（扩大一倍，或扩大sqrt2）。因为整数不用考虑浮点误差，而且运算比浮点快。

一。点，线，面，形基本关系，点积叉积的理解

POJ 2318 TOYS（推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=2318
POJ 2398 Toy Storage（推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=2398
一个矩形，有被若干直线分成N个格子，给出一个点的坐标，问你该点位于哪个点中。
知识点：其实就是点在凸四边形内的判断，若利用叉积的性质，可以二分求解。

POJ 3304 Segments
http://acm.pku.edu.cn/JudgeOnline/problem?id=3304
知识点：线段与直线相交，注意枚举时重合点的处理

POJ 1269 Intersecting Lines
http://acm.pku.edu.cn/JudgeOnline/problem?id=1269
知识点：直线相交判断，求相交交点

POJ 1556 The Doors （推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1556
知识点：简单图论＋简单计算几何，先求线段相交，然后再用Dij求最短路。

POJ 2653 Pick-up sticks
http://acm.pku.edu.cn/JudgeOnline/problem?id=2653
知识点：还是线段相交判断

POJ 1066 Treasure Hunt
http://acm.pku.edu.cn/JudgeOnline/problem?id=1066
知识点：线段相交判断，不过必须先理解“走最少的门”是怎么一回事。

POJ 1410 Intersection
http://acm.pku.edu.cn/JudgeOnline/problem?id=1410
知识点：线段与矩形相交。正确理解题意中相交的定义。
详见：http://hi.baidu.com/novosbirsk/blog/item/68c682c67e8d1f1d9d163df0.html

POJ 1696 Space Ant （推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1696
德黑兰赛区的好题目。需要理解点积叉积的性质

POJ 3347 Kadj Squares
http://acm.pku.edu.cn/JudgeOnline/problem?id=3347
本人的方法极度猥琐。复杂的线段相交问题。这个题目是计算几何的扩大数据运算的典型应用，扩大根号2倍之后就避免了小数。

POJ 2826 An Easy Problem?! （推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=2826
问：两条直线组成一个图形，能容纳多少雨水。很不简单的Easy Problem，要考虑所有情况。你不看discuss看看能否AC。（本人基本不能）提示一下，水是从天空垂直落下的。

POJ 1039 Pipe
http://acm.pku.edu.cn/JudgeOnline/problem?id=1039
又是线段与直线相交的判断，再加上枚举的思想即可。

POJ 3449 Geometric Shapes
http://acm.pku.edu.cn/JudgeOnline/problem?id=3449
判断几何体是否相交，不过输入输出很恶心。
此外，还有一个知识点，就是给出一个正方形（边不与轴平行）的两个对角线上的顶点，需要你求出另外两个点。必须掌握其方法。

POJ 1584 A Round Peg in a Ground Hole
http://acm.pku.edu.cn/JudgeOnline/problem?id=1584
知识点：点到直线距离，圆与多边形相交，多边形是否为凸

POJ 2074 Line of Sight （推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=2074
与视线问题的解法，关键是求过两点的直线方程，以及直线与线段的交点。数据有一个trick，要小心。

二。凸包问题

POJ 1113 Wall
http://acm.pku.edu.cn/JudgeOnline/problem?id=1113
知识点：赤裸裸的凸包问题，凸包周长加上圆周。

POJ 2007 Scrambled Polygon
http://acm.pku.edu.cn/JudgeOnline/problem?id=2007
知识点：凸包，按极角序输出方案

POJ 1873 The Fortified Forest （推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1873
World Final的水题，先求凸包，然后再搜索。由于规模不大，可以使用位运算枚举。
详见：http://hi.baidu.com/novosbirsk/blog/item/333abd54c7f22c52574e0067.html

POJ 1228 Grandpa's Estate （推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1228
求凸包顶点数目，很多人求凸包的模板是会多出点的，虽然求面积时能得到正确答案，但是在这个题目就会出问题。此外，还要正确理解凸包的性质。

POJ 3348 Cows
http://acm.pku.edu.cn/JudgeOnline/problem?id=3348
凸包面积计算

三。面积问题，公式问题

POJ 1654 Area
http://acm.pku.edu.cn/JudgeOnline/problem?id=1654
知识点：利用有向面积（叉积）计算多边形面积

POJ 1265 Area
http://acm.pku.edu.cn/JudgeOnline/problem?id=1265
POJ 2954 Triangle
http://acm.pku.edu.cn/JudgeOnline/problem?id=2954
Pick公式的应用，多边形与整点的关系。（存在一个GCD的关系）

四。半平面交

半平面交的主要应用是判断多边形是否存在核，还可以解决一些与线性方程组可行区域相关的问题（就是高中时的那些）。

POJ 3335 Rotating Scoreboard
http://acm.pku.edu.cn/JudgeOnline/problem?id=3335
POJ 3130 How I Mathematician Wonder What You Are!
http://acm.pku.edu.cn/JudgeOnline/problem?id=3130
POJ 1474 Video Surveillance
http://acm.pku.edu.cn/JudgeOnline/problem?id=1474
知识点：半平面交求多边形的核，存在性判断

POJ 1279 Art Gallery
http://acm.pku.edu.cn/JudgeOnline/problem?id=1279
半平面交求多边形的核，求核的面积

POJ 3525 Most Distant Point from the Sea （推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3525
给出一个多边形，求里面的一个点，其距离离多边形的边界最远，也就是多边形中最大半径圆。
可以使用半平面交+二分法解。二分这个距离，边向内逼近，直到达到精度。

POJ 3384 Feng Shui （推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3384
半平面交实际应用，用两个圆覆盖一个多边形，问最多能覆盖多边形的面积。
解法：用半平面交将多边形的每条边一起向“内”推进R，得到新的多边形，然后求多边形的最远两点。

POJ 1755 Triathlon （推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1755
半平面交判断不等式是否有解。注意不等式在转化时正负号的选择，这直接影响到半平面交的方向。

POJ 2540 Hotter Colder
http://acm.pku.edu.cn/JudgeOnline/problem?id=2540
半平面交求线性规划可行区域的面积。

POJ 2451 Uyuw's Concert
http://acm.pku.edu.cn/JudgeOnline/problem?id=2451
Zzy专为他那篇nlogn算法解决半平面交问题的论文而出的题目。

五。计算几何背景，实际上解题的关键是其他问题（数据结构、组合数学，或者是枚举思想）
若干道经典的离散化＋扫描线的题目，ACM选手必做题目

POJ 1151 Atlantis （推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1151
POJ 1389 Area of Simple Polygons
http://acm.pku.edu.cn/JudgeOnline/problem?id=1389
矩形离散化，线段树处理，矩形面积求交

POJ 1177 Picture （推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1177
矩形离散化，线段树处理，矩形交的周长，这个题目的数据比较强。线段树必须高效。

POJ 3565 Ants （推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3565
计算几何中的调整思想，有点像排序。要用到线段相交的判断。
详见：http://hi.baidu.com/novosbirsk/blog/item/fb668cf0f362bec47931aae2.html

POJ 3695 Rectangles
http://acm.pku.edu.cn/JudgeOnline/problem?id=3695
又是矩形交的面积，但是由于是多次查询，而且矩形不多，使用组合数学中的容斥原理解决之最适合。线段树是通法，但是除了线段树，还有其他可行的方法。

POJ 2002 Squares
http://acm.pku.edu.cn/JudgeOnline/problem?id=2002
枚举思想，求平面上若干个点最多能组成多少个正方形，点的Hash

POJ 1434 Fill the Cisterns!（推荐）
http://acm.pku.edu.cn/JudgeOnline/problem?id=1434
一开始发昏了，准备弄个线段树。其实只是个简单的二分。

六。随机算法
POJ 2420 A Star not a Tree?
http://acm.pku.edu.cn/JudgeOnline/problem?id=2420
多边形的费马点。所谓费马点，就是多边形中一个点P，该点到其他点的距离之和最短。四边形以上的多边形没有公式求费马点，因此可以使用随机化变步长贪心法。
详见：http://hi.baidu.com/novosbirsk/blog/item/75983f138499f825dd54019b.html

七。解析几何
这种题目本人不擅长，所以做得不多，模板很重要。当然，熟练运用叉积、点积的性质还是很有用的。
POJ 1375 Intervals
http://acm.pku.edu.cn/JudgeOnline/problem?id=1375
知识点：过圆外一点求与圆的切线

POJ 1329 Circle Through Three Points
http://acm.pku.edu.cn/JudgeOnline/problem?id=1329
求三角形外接圆

POJ 2354 Titanic
http://acm.pku.edu.cn/JudgeOnline/problem?id=2354
求球面上两个点的距离，而且给的是地理经纬坐标。

POJ 1106 Transmitters
http://acm.pku.edu.cn/JudgeOnline/problem?id=1106
角度排序，知道斜率求角度，使用atan函数。

POJ 1673 EXOCENTER OF A TRIANGLE
http://acm.pku.edu.cn/JudgeOnline/problem?id=1673
可以转化为三角形的垂心问题。

八。旋转卡壳

POJ 2187 Beauty Contest
http://acm.pku.edu.cn/JudgeOnline/problem?id=2187
凸包求最远点对。可以暴力枚举，也可以使用旋转卡壳。

POJ 3608 Bridge Across Islands（难）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3608
两个凸包的最近距离。本人的卡壳始终WA。郁闷。

九。其他问题
POJ 1981 Circle and Points
http://acm.pku.edu.cn/JudgeOnline/problem?id=1981
求单位圆最多能覆盖平面上多少个点

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/linleiqin/archive/2010/04/04/5450150.aspx

bluedream 2010-06-17 15:58 发表评论

POJ 2593 Max Sequence

bluedream — Wed, 16 Jun 2010 03:10:00 GMT

Description

Give you N integers a1, a2 ... aN (|ai| <=1000, 1 <= i <= N).

You should output S.

Input

The input will consist of several test cases. For each test case, one integer N (2 <= N <= 100000) is given in the first line. Second line contains N integers. The input is terminated by a single line with N = 0.

Output

For each test of the input, print a line containing S.

Sample Input

5
-5 9 -5 11 20
0

Sample Output

Source

1#include <cstdio>
2//#include
3using namespace std;
4int a[100002],b[100002],c[100002];
5int main(){
6
7/*    fstream fin("2593.txt");
8    if(!fin){
9        cout<<"can not open the file "<10        system("pause");
11        return 0;
12    }*/
13    int n;
14    int max;
15    int tmp=0,sum=0;
16    scanf("%d",&n);
17
18    while(n){
19        for(int i=0;i<n;i++){
20            scanf("%d",&a[i]);
21            b[i]=c[i]=0;
22        }
23
24       tmp=0;
25       sum=-1000000;
26       for(int j=0;j<n;j++){
27           if(tmp>0)tmp+=a[j];
28           else {
29               tmp=a[j];
30           }
31           if(tmp>sum){
32               sum=tmp;
33           }
34           b[j]=sum;
35       }
36       tmp=0;
37       sum=-1000000;
38       for(int j=n-1;j>=0;j--){
39           if(tmp>0)tmp+=a[j];
40           else {
41               tmp=a[j];
42           }
43           if(tmp>sum){
44               sum=tmp;
45           }
46           c[j]=sum;
47       }
48       max=-11000000;
49       for(int j=0;j<n-1;j++){
50           if(b[j]+c[j+1]>max){
51               max=b[j]+c[j+1];
52               //cout<<"bj"<53               //cout<<"c[j+1]"<
54           }
55       }
56       printf("%d",max);
57       //system("pause");
58       scanf("%d",&n);
59   }
60    //fin.close();
61    return 0;
62}
63
64
65
66
67

bluedream 2010-06-16 11:10 发表评论

[转] HDU 动态规划（46道题目）倾情奉献~ 只提供思路与状态转移方程

bluedream — Mon, 07 Jun 2010 14:05:00 GMT

转载自腾云华夏

Robberies http://acm.hdu.edu.cn/showproblem.php?pid=2955
背包;第一次做的时候把概率当做背包(放大100000倍化为整数):在此范围内最多能抢多少钱最脑残的是把总的概率以为是抢N家银行的概率之和… 把状态转移方程写成了f[j]=max{f[j],f[j-q[i].v]+q[i].money}(f[j]表示在概率j之下能抢的大洋);

正确的方程是:f[j]=max(f[j],f[j-q[i].money]*q[i].v) 其中,f[j]表示抢j块大洋的最大的逃脱概率,条件是f[j-q[i].money]可达,也就是之前抢劫过;
始化为:f[0]=1,其余初始化为-1 (抢0块大洋肯定不被抓嘛)

最大报销额 http://acm.hdu.edu.cn/showproblem.php?pid=1864
又一个背包问题,对于每张发票,要么报销,要么不报销,0-1背包,张数即为背包;
转移方程:f[j]=max(f[j],f[j-1]+v[i]);
恶心地方:有这样的输入数据 3 A:100 A:200 A:300

最大连续子序列 http://acm.hdu.edu.cn/showproblem.php?pid=1231
状态方程:sum[i]=max(sum[i-1]+a[i],a[i]);最后从头到尾扫一边
也可以写成:
Max=a[0];
Current=0;
for(i=0;i       if(Current<0)
              Current=a[i];
       else
              Current+=a[i];
       if(Current>Max)
              Max=Current;
}

max sum http://acm.hdu.edu.cn/showproblem.php?pid=1003
同上,最大连续子序列

Largest Rectangle http://acm.hdu.edu.cn/showproblem.php?pid=1506
对于每一块木板,Area=height[i]*(j-k+1) 其中,j<=x<=k,height[x]>=height[i];找j,k成为关键,一般方法肯定超时,利用动态规划,如果它左边高度大于等于它本身,那么它左边的左边界一定满足这个性质,再从这个边界的左边迭代下去
for(i=1;i<=n;i++){
while(a[l[i]-1]>=a[i])
l[i]=l[l[i]-1];

}

for(i=n;i>=1;i–)
{
while(a[r[i]+1]>=a[i])
r[i]=r[r[i]+1];
}

City Game http://acm.hdu.edu.cn/showproblem.php?pid=1505
1506的加强版,把2维转换化成以每一行底,组成的最大面积;(注意处理连续与间断的情况);

Bone Collector http://acm.hdu.edu.cn/showproblem.php?pid=2602
简单0-1背包,状态方程:f[j]=max(f[j],f[j-v[i]]+w[i])

Super Jumping http://acm.hdu.edu.cn/showproblem.php?pid=1087
最大递增子段和,状态方程:sum[j]=max{sum[i]}+a[j]; 其中,0<=i<=j,a[i]

命运http://acm.hdu.edu.cn/showproblem.php?pid=2571
状态方程:sum[i][j]=max{sum[i-1][j],sum[i][k]}+v[i][j];其中1<=k<=j-1,且k是j的因子

Monkey And Banana http://acm.hdu.edu.cn/showproblem.php?pid=1069
状态方程:f[j]=max{f[i]}+v[j];其中,0<=i<=j,w[i]

Big Event in HDU http://acm.hdu.edu.cn/showproblem.php?pid=1171
一维背包,逐个考虑每个物品带来的影响,对于第i个物品:if(f[j-v[i]]==0) f[j]=0;
其中,j为逆序循环,且j>=v[i]

数塔http://acm.hdu.edu.cn/showproblem.php?pid=2084
自底向上:dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+v[i][j];

免费馅饼http://acm.hdu.edu.cn/showproblem.php?pid=1176
简单数塔
自底向上计算:dp[i][j]=max(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1])+v[i][j];处理边界

I Need A Offer http://acm.hdu.edu.cn/showproblem.php?pid=1203
简单0-1背包,题目要求的是至少收到一份Offer的最大概率,我们得到得不到的最小概率即可,状态转移方程:f[j]=min(f[j],f[j-v[i]]*w[i]);其中,w[i]表示得不到的概率,(1-f[j])为花费j元得到Offer的最大概率

FATE http://acm.hdu.edu.cn/showproblem.php?pid=2159
二维完全背包,第二层跟第三层的要顺序循环;(0-1背包逆序循环);状态可理解为,在背包属性为 {m(忍耐度), s(杀怪个数)} 里最多能得到的经验值,之前的背包牺牲体积,这个背包牺牲忍耐度跟个数
注意: 最后扫的时候外层循环为忍耐度,内层循环为杀怪个数,因为题目要求出剩余忍耐度最大,没有约束杀怪个数,一旦找到经验加满的即为最优解;
状态转移方程为: f[j][k]=max(f[j][k],f[j-v[i]][k-1]+w[i]); w[i]表示杀死第i个怪所得的经验值,v[i]表示消耗的忍耐度

How To Type http://acm.hdu.edu.cn/showproblem.php?pid=2577
用两个a,b数组分别记录Caps Lock开与关时打印第i个字母的最少操作步骤;
而对于第i个字母的大小写还要分开讨论:
Ch[i]为小写: a[i]=min(a[i-1]+1,b[i-1]+2);不开灯直接字母,开灯则先关灯再按字母,最后保持不开灯; b[i]=min(a[i-1]+2,b[i-1]+2);不开灯则先按字母再开灯,开灯则Shift+字母(比关灯,按字母再开灯节省步数),最后保持开灯;
Ch[i]为大写: a[i]=min(a[i-1]+2,b[i-1]+2); b[i]=min(a[i-1]+2,b[i-1]+1)

最后,b[len-1]++,关灯嘛O(∩_∩)O~

Coins http://acm.hdu.edu.cn/showproblem.php?pid=2844
类似于HDU1171 Big Event In HDU,一维DP,可达可不达

Beans http://acm.hdu.edu.cn/showproblem.php?pid=2845
横竖分别求一下不连续的最大子段和;
状态方程: Sum[i]=max(sum[j])+a[i];其中,0<=j

Largest Submatrix http://acm.hdu.edu.cn/showproblem.php?pid=2870
枚举a,b,c 最大完全子矩阵,类似于HDU1505 1506

Matrix Swapping II http://acm.hdu.edu.cn/showproblem.php?pid=2830
最大完全子矩阵,以第i行为底,可以构成的最大矩阵,因为该题可以任意移动列,所以只要大于等于height[i]的都可以移动到一起,求出height>=height[i]的个数即可,这里用hash+滚动,先求出height[i]出现的次数,然后逆序扫一遍hash[i]+=hash[i+1];

最少拦截系统http://acm.hdu.edu.cn/showproblem.php?pid=1257
两种做法,一是贪心,从后往前贪;二是DP;
if(v[i]>max{dp[j]}) (0<=jdp[len++]=v[i];

Common Subsequence http://acm.hdu.edu.cn/showproblem.php?pid=1159
经典DP,最长公共子序列
Len[i][j]={len[i-1][j-1]+1,(a[i]==b[j]); max(len[i-1][j],len[i][j-1])}
初始化的优化:
for(i=0;i       for(j=0;j              len[i][j]=0;
for(i=1;i<=a;i++)
       for(j=1;j<=b;j++)
              if(ch1[i-1]==ch2[j-1])
                     len[i][j]=len[i-1][j-1]+1;
              else
                     len[i][j]=max(len[i-1][j],len[i][j-1]);

★ 搬寝室http://acm.hdu.edu.cn/showproblem.php?pid=1421
状态Dp[i][j]为前i件物品选j对的最优解
当i=j*2时,只有一种选择即 Dp[i-2][j-1]+(w[i]-w[i-1])^2
当i>j*2时,Dp[i][j] = min(Dp[i-1][j],Dp[i-2][j-1]+(w[j]-w[j-1])^2)

★ Humble Numbers http://acm.hdu.edu.cn/showproblem.php?pid=1058
如果一个数是Humble Number,那么它的2倍,3倍,5倍,7倍仍然是Humble Number
定义F[i]为第i个Humble Number
F[n]=min(2*f[i],3*f[j],5*f[k],7*f[L]), i,j,k,L在被选择后相互移动
(通过此题理解到数组有序特性)

★ Doing Homework Again http://acm.hdu.edu.cn/showproblem.php?pid=1789
这题为贪心,经典题;
切题角度,对于每个任务要么在截至日期前完成要么被扣分;所以考虑每个人物的完成情况即可;由于每天只能完成一个任务,所以优先考虑分值较大的任务,看看该任务能不能完成,只要能完成,即使提前完成,占了其他任务的完成日期也没关系,因为当前任务的分值最大嘛,而对于能完成的任务能拖多久就拖多久,以便腾出更多时间完成其他任务;

How Many Ways http://acm.hdu.edu.cn/showproblem.php?pid=1978
两种D法,一是对于当前的点,那些点可达;二是当前点可达那些点;
明显第二种方法高,因为第一种方法有一些没必要的尝试;
Dp[i][j]+=Dp[ii][jj]; (map[ii][jj]>=两点的曼哈顿距离)
值得优化的地方,每两点的曼哈顿距离可能不止求一次,所以预处理一下直接读取

珍惜现在感恩生活http://acm.hdu.edu.cn/showproblem.php?pid=2191
每个物品最多可取n件,多重背包;
利用二进制思想,把每种物品转化为几件物品,然后就成为了0-1背包

Piggy-Bank http://acm.hdu.edu.cn/showproblem.php?pid=1114
完全背包;常规背包是求最大值,这题求最小值;
只需要修改一下初始化,f[0]=0,其他赋值为+∞即可;
状态转移方程:f[i][V]=max{f[i-1][V],f[i-1][V-k*v[i]]+k*w[i]},其中0<=k*v[i]<=V

★ Max Sum Plus Plus http://acm.hdu.edu.cn/showproblem.php?pid=1024
1. 对于前n个数, 以v[n]为底取m段:
当n==m时,Sum[m][n]=Sum[m-1][n-1]+v[n],第n个数独立成段;
当n>m时, Sum[m][n]=max{Sum[m-1][k],Sum[m][n-1]}+v[n]; 其中,m-1<=k2. 空间的优化:
通过状态方程可以看出,取m段时,只与取m-1段有关,所以用滚动数组来节省空间

FatMouse’s Speed http://acm.hdu.edu.cn/showproblem.php?pid=1160
要求:体重严格递增,速度严格递减,原始顺序不定
按体重或者速度排序,即顺数固定后转化为最长上升子序列问题
Dp[i]表示为以第i项为底构成的最长子序列,Dp[i]=max(dp[j])+1,其中0<=jw[j]&&s[i]

Cstructing Roads http://acm.hdu.edu.cn/showproblem.php?pid=1025
以p或者r按升序排列以后,问题转化为最长上升子序列
题目数据量比较大,只能采取二分查找,n*log(n)的算法
用一个数组记录dp[]记录最长的子序列,len表示长度,如果a[i]>dp[len], 则接在后面,len++; 否则在dp[]中找到最大的j,满足dp[j]

FatMouse Chees http://acm.hdu.edu.cn/showproblem.php?pid=1078
Dp思想,用记忆化搜索;简单题,处理好边界;

To the Max http://acm.hdu.edu.cn/showproblem.php?pid=1081
最大子矩阵
把多维转化为一维的最大连续子序列;(HDU1003)

龟兔赛跑http://acm.hdu.edu.cn/showproblem.php?pid=2059
未总结

★ Employment Planning http://acm.hdu.edu.cn/showproblem.php?pid=1158
状态表示: Dp[i][j]为前i个月的留j个人的最优解;Num[i]<=j<=Max{Num[i]};
j>Max{Num[i]}之后无意义,无谓的浪费记Max_n=Max{Num[i]};
Dp[i-1]中的每一项都可能影响到Dp[i],即使Num[i-1]<所以利用Dp[i-1]中的所有项去求Dp[i];
对于Num[i]<=k<=Max_n, 当k当k>j时, 解雇然后求出最小值
Dp[i][j]=min{Dp[i-1][k…Max_n]+(招聘,解雇,工资);

Dividing http://acm.hdu.edu.cn/showproblem.php?pid=1059
一维Dp Sum为偶数的时候判断Dp[sum/2]可不可达

Human Gene Factions http://acm.hdu.edu.cn/showproblem.php?pid=1080
状态转移方程:
f[i][j]=Max(f[i-1][j-1]+r[a[i]][b[j]], f[i][j-1]+r[‘-‘][b[j]],f[i-1][j]+r[a[i]][‘-‘]);Pearls

http://acm.hdu.edu.cn/showproblem.php?pid=1300
Dp[i]=min{Dp[j]+V}, 0<=j

Zipper http://acm.hdu.edu.cn/showproblem.php?pid=1501
Dp[i][j]=

★Fast Food http://acm.hdu.edu.cn/showproblem.php?pid=1227
这里需要一个常识:在i到j取一点使它到区间每一点的距离之和最小,这一点为(i+j)/2用图形即可证明;
Dp[i][j]=max{Dp[i-1][k]+cost[k+1][j] 其中,(i-1)<=k

Warcraft http://acm.hdu.edu.cn/showproblem.php?pid=3008
比赛的时候这道DP卡到我网络中心停电!!! 卧槽~
因为你没有回血效应,所以你挂掉的时间是一定的;
用Dp[i][j]表示第i秒剩余j个单位的MP时怪物所剩的血量; 注意必须是剩余,也就是说,初始化的时候,DP[0][100]=100; 其他Dp[0]状态都不合法,因为没有开战的时候你的MP是满的
以前的Dp都是利用前面得到的最优解来解决,而这题的麻烦点是MP在攻击过后要自动恢复x个单位;用当前的状态的状态推下一状态,仔细想想也未尝不可;状态转移方程为:
Dp[i+1][j-sk[k].mp+x]=min(Dp[i+1][j-sk[k].mp+x],Dp[i][j]+sk[k].at; 释放第K种技能,物理攻击可以看成是at=1,mp=0 的魔法;

Regular Words http://acm.hdu.edu.cn/showproblem.php?pid=1502
F[a][b][c]=F[a-1][b][c]+F[a][b-1][c]+F[a][b][c-1];
a>=b>=c;

Advanced Fruits http://acm.hdu.edu.cn/showproblem.php?pid=1503
最长公共子序列的加强版

★ Doing Homework http://acm.hdu.edu.cn/showproblem.php?pid=1074
这题用到位压缩;
那么任务所有的状态有2^n-1种
状态方程为:Dp[next]=min{Dp[k]+i的罚时} 其中,next=k+(1<>i的奇偶性决定状态k
具体实现为: 对每种状态遍历n项任务,如果第i项没有完成,则计算出Dp[next]的最优解

Free DIY Tour http://acm.hdu.edu.cn/showproblem.php?pid=1224
简单的数塔Dp,考察的是细节的处理;
Dp[i]=Max{Dp[j]}+v[i] 其中j->i为通路;
v[n+1]有没有初始化,Dp数组有没有初始化
这题不能用想当然的”最长路”来解决,这好像是个NP问题解决不了的

重温世界杯http://acm.hdu.edu.cn/showproblem.php?pid=1422
这题的状态不难理解,状态表示为,如果上一个城市剩下的钱不为负,也就是没有被赶回杭电,则再考虑它对下一个城市的影响;如果上一个城市剩下的前加上当前城市的前大于当前城市的生活费,那么Dp[i]=Dp[i-1]+1;
值得注意的而是这题的数据为100000;不可能以每个城市为起点来一次Dp,时间复杂度为n^2;足已超时;
我是这样处理的,在保存的数据后面再接上1…n的数据,这样扫描一遍的复杂度为n;再加一个优化,当Dp[i]==

n时,也就是能全部游完所有城市的时候,直接break;

bluedream 2010-06-07 22:05 发表评论

矩阵连乘问题

bluedream — Sun, 06 Jun 2010 12:12:00 GMT

给定n个矩阵，给这n个矩阵加若干个括号，使得这n个矩阵所用的乘法次数最少。

动态规划的解法：
m[i][j]=min{ m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]}

其中 i<=kcode:

1#include <iostream>
2#include <vector>
3#include <fstream>
4using namespace std;
5int m[100][100],s[100][100];
6int p[100];
7int sovle(int n){
8    int i,j,k,r;
9    for(i=1;i<=n;i++)m[i][i]=0;
10    for(r=2;r<=n;r++){
11        for(i=1;i<=n-r+1;i++){
12            j=i+r-1;
13            //cout<<"j= "<
14            int t=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];
15            for(k=i+1;k<j;k++){
16                int mt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
17                if(t>mt){t=mt;}
18            }
19            m[i][j]=t;
20        }
21    }
22    cout<<"**"<<m[1][n+3]<<endl;
23    return m[1][n];
24}
25
26
27
28int main(){
29   fstream fin("matrix.txt");
30   int n;
31   fin>>n;
32   for(int i=0;i<n;i++){
33      fin>>p[i];
34   }
35
36   cout<<sovle(n-1)<<endl;
37
38   system("pause");
39   fin.close();
40
41   return 0;
42}
43

bluedream 2010-06-06 20:12 发表评论

最小m段和问题

bluedream — Mon, 31 May 2010 03:10:00 GMT

最小m段和问题

给定 n 个整数组成的序列，现在要求将序列分割为 m 段，每段子序列中
的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达
到最小？

动态规划的解法：

1. 阶段数为m.

2. 状态转移方程：

f[i][j]=min max{ f[i][1]-f[k][1],f[k][j-1]}

其中1<=k

初态：f[i][1]=f[i-1][1]+a[i]

最优值为f[n][m]。

3. 对于第j阶段中的每个 i, (j<=i <=n)，考虑将1到i的序列分为j段子序列,且第j段序列从k开始到i，
由最优子结构性质，只需比较第j段序列和第j-1阶段的最优值即可。

决策变量：第j段序列分配i-k个元素

源代码：

1#include <iostream>
2#include <fstream>
3using namespace std;
4
5int main(){
6    int n,m;
7    ifstream fin("sum1.in");
8    if(!fin){
9        cout<<"can not open the file !"<<endl;
10        system("pause");
11        return 0;
12    }
13
14    fin>>n>>m;
15    int i=n;
16    int a[n+1];
17    for(i=1;i<=n;i++){
18        fin>>a[i];
19    }
20    fin.close();
21    int f[n+1][m+1];
22    //初始化第一阶段信息
23    f[0][1]=0;
24    for(int i=1;i<=n;i++){
25        f[i][1]=f[i-1][1]+a[i];
26    }
27    int tmp,maxN=0;
28    for(int j=2;j<=m;j++){
29        for(int i=j;i<=n;i++){
30            tmp=1000000;
31            for(int k=1;k<i;k++){
32                maxN=std::max(f[i][1]-f[k][1],f[k][j-1]) ;
33                if(tmp>maxN)tmp=maxN;
34            }
35           f[i][j]=tmp;
36        }
37    }
38    cout<<f[n][m]<<endl;
39    system("pause");
40     return 0;
41    }
42
43
44

测试：
9 3
9 8 7 6 5 4 3 2 1

输出
17

2010年5月31日11:08:38

bluedream 2010-05-31 11:10 发表评论