老公说年轻的时候应该是要留下点什么。我写过很多东西， 但最后都没有坚持下去，我做百度空间，QQ空间， 还有校内。 QQ空间在大学坚持了4年，出来工作就觉得总是没有时间可以写了，久了以后觉得就算有时间也写不出来了。
现在开始在工作之余学习，当老公在看书的时候我总是骚扰他， 久了以后觉得自己太不像话，不只自己不学习还拖人后腿。 老公在给自己购书的时候会给我挑上两本，强迫我看完，想缓解一下被骚扰的痛苦吧。感谢之余还得说，我改不了骚扰人的习惯了……我也许会努力一点。
把这个blog 写下去，认真地写，留下一些东西。
我有的时候很无聊的， 比如说：脚丫两个。
脚丫4个。
以后会有6个脚丫的，呵呵。
在很久很久以前，有一个动物村庄，那里是猪的乐园（^_^），村民们勤劳、勇敢、善良、团结……
不过有一天，最小的小小猪生病了，而这种病是极其罕见的，因此大家都没有储存这种药物。所以晴天小猪自告奋勇，要去采取这种药草。于是，晴天小猪的传奇故事便由此展开……
【描述 Description】
这一天，他来到了一座深山的山脚下，因为只有这座深山中的一位隐者才知道这种药草的所在。但是上山的路错综复杂，由于小小猪的病情，晴天小猪想找一条需时最少的路到达山顶，但现在它一头雾水，所以向你求助。
山用一个三角形表示，从山顶依次向下有1段、2段、3段等山路，每一段用一个数字T（1<=T<=100）表示，代表晴天小猪在这一段山路上需要爬的时间，每一次它都可以朝左、右、左上、右上四个方向走（**注意**：在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段）。
晴天小猪从山的左下角出发，目的地为山顶，即隐者的小屋。
【输入格式 Input Format】
第一行有一个数n（2<=n<=1000），表示山的高度。
从第二行至第n+1行，第i+1行有i个数，每个数表示晴天小猪在这一段山路上需要爬的时间。
【输出格式 Output Format】
一个数，即晴天小猪所需要的最短时间。
【算法描述】
f[i,j]=min{f[i-1,j-1],f[i-1,j],f[i,j-1],f[i,j+1]}+a[i,j]
最原始的方程就是三角形那个，但是在此基础上还需要一些改进。。
1.DP有环怎么办?
别急,先别想着放弃DP,有时候环是可以避免的.这里在每一行中为避免相邻两格左右移动产生的环,可以先推向左的,再推向右的,而同向移动产生的那个“大”环就麻烦一点.其实有个很简单的窍门:先记录从下一行转移来的最优值,然后在本行中寻找代价最小的点,以这个点为起点分别向左向右推,因为最小的点显然是不需要从两侧的点过来的.这样就没有后效性了..
2.递推的顺序:
递推有两种顺序,可以根据当前状态值推出所有可能的后继状态,也可以根据所有当前状态可能的前驱来推当前值,很多时候,当问题的状态比较有规律时,这两种方法是不相上下的.但是其他情况下一不小心就可能搞错.比如这题题目告诉我们的是从一个状态可行的所有走法(共四种),所以根据这个顺序去编是最保险的。因为这里一个状态的前驱不一定只是四个,边缘的点是特例,可能会有5个来源,所以DP的时候不要随便换状态转移顺序.
【代码】
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 | #include <stdio.h> #include <stdlib.h> #include <string.h> #define min(a,b)(a<b?a:b) int a[1002][1002]; int b[1002][1002]; int main() { int n, i, j; scanf("%d", &n); for (i = 1; i <= n; i++) { for (j = 1; j <= i; j++) scanf("%d", &a[i][j]); } for (i = 1; i <= n; i++) { a[i][0] = a[i][i]; a[i][i + 1] = a[i][1]; } memset(b, 0, sizeof(int) * 1002 * 1002); for (i = 1; i <= n; i++) //最下面一层 b[n][i] = b[n][i - 1] + a[n][i]; b[n][n] = a[n][1] + a[n][n]; for (i = n - 1; i >= 2; i--) //求最下面一层每个位置的最小 if (b[n][i] > b[n][i + 1] + a[n][i]) b[n][i] = b[n][i + 1] + a[n][i]; for (i = n - 1; i >= 1; i--) //DP上面的每一层，此为DP的阶段 { for (j = 1; j <= i; j++) //状态转移 { if (j == 1) //对于每一个点，要考虑下 b[i][j] = min(b[i + 1][i + 1], min(b[i + 1][j], b[i + 1][j + 1])) + a[i][j]; else if (j != 1 && j != i) b[i][j] = min(b[i][j - 1],min(b[i + 1][j], b[i + 1][j + 1])) + a[i][j]; else if (j == i) b[i][j] = min(b[i][j - 1], min(b[i + 1][1], min(b[i + 1][j], b[i + 1][j + 1]))) + a[i][j]; } for (j = 1; j <= i; j++) //本层的DP 从前往后 { if (j == 1) //特殊处理 b[i][j] = min(b[i][j], b[i][i] + a[i][j]); else b[i][j] = min(b[i][j], b[i][j - 1] + a[i][j]); } for (j = i; j >= 1; j--)//本层的DP 从后往前 { if (j == i) //特殊处理 b[i][j] = min(b[i][j], b[i][1] + a[i][j]); else b[i][j] = min(b[i][j], b[i][j + 1] + a[i][j]); } } printf("%d\n", b[1][1]); return 0; } |
/*
动态规划。
将n个村庄按坐标递增依次编号为1，2，……，n，各个邮局的坐标为a[1..n]，
状态表示描述为：f[i,j]表示在前i个村庄建立j个邮局的最小距离和。所以，f[n,p]即为问题的解，
且状态转移方程和边界条件为：
f[j,1]=w[1,j];
f[i,j]=min{f[k,j - 1]+w[k+1,i]}; (i≤j, j – 1≤k≤i)
其中w[i,j]表示在a[i..j]之间建立一个邮局的最小距离和，可以证明，当仅建立一个邮局时，
最优解出现在中位数，于是，我们有：
w[i,j]=w[i,j]+|a[k]-a[t]| (1<=i1
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
#include <stdio.h>
#include <string.h>
#include <math.h>
#define min(a,b) a<b?a:b
int main()
{
int n, m, a[301], f[301][31], i, j , k, w[301][301];
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (i = 0; i <= n; i++)
for (j = 0; j <= m; j++)
f[i][j] = 100000;
memset(w, 0, sizeof(w));
for (i = 1; i <= n; i++)
{
for (j = i; j <= n; j++)
{
for (k = i ; k <= j; k++)
w[i][j] += abs(a[k] - a[(i + j) / 2]);
}
}
for (i = 1; i <= n; i++)
f[i][1] = w[1][i];
for (j = 2; j <= m; j++)
{
for (i = j; i <= n; i++)
{
for (k = j - 1; k < i; k++)
{
f[i][j] = min(f[i][j], f[k][j - 1] + w[k + 1][i]);
}
}
}
printf("%d\n", f[n][m]);
return 0;
}