問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1157思路:
比較容易的動(dòng)態(tài)規(guī)劃，這里提供兩種思路，其中第二種更優(yōu)
另外，居然在寫代碼的時(shí)候?qū)?xFFFFFFFF當(dāng)作最小的int值，汗...
代碼(方案1)
1 /* 63MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_F 101
6 #define MAX_V 101
7 #define INF 0xF0000000
8 int values[MAX_F][MAX_V];
9 int table[MAX_F][MAX_V];
10 int f, v;
11
12 /*
13 * f[i][j] represent the maximum aesthetic values for putting the first [1..i]
14 * bunches in the first [1..j] vases, so:
15 * f[i][j] = max (f[i-1][k] + tmp), i-1<=k<j
16 */
17 dp()
18 {
19 int i, j, k, p, t, up, tmp, max;
20 table[1][1] = values[1][1];
21 for(j=2; j<=v-f+1; j++) /* i = 1 */
22 table[1][j] = values[1][j]>table[1][j-1] ? values[1][j] : table[1][j-1];
23 for(i=2; i<=f; i++) {
24 up = v-f+i;
25 for(j=i; j<=up; j++) {
26 max = INF;
27 for(k=i-1; k<j; k++) {
28 t = values[i][k+1];
29 for(p=k+2; p<j; p++)
30 t = values[i][p] > t ? values[i][p] : t;
31 tmp = table[i-1][k] + t;
32 max = tmp > max ? tmp : max;
33 }
34 table[i][j] = max;
35 }
36 }
37 return table[f][v];
38 }
39
40 int
41 main(int argc, char **argv)
42 {
43 int i, j;
44 while(scanf("%d %d", &f, &v)!=EOF) {
45 for(i=1; i<=f; i++)
46 for(j=1; j<=v; j++)
47 scanf("%d", values[i]+j);
48 printf("%d\n", dp());
49 }
50 }
代碼(方案2)
1 /* 32MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_F 101
6 #define MAX_V 101
7 #define INF 0xF0000000
8 int values[MAX_F][MAX_V];
9 int table[MAX_F][MAX_V];
10 int f, v;
11
12 /*
13 * f[i][j] represent the maximum aesthetic values for putting the i(th) bunch
14 * in the j(th) vases(total i bunches), so:
15 * f[i][j] = max(f[i-1][k])+values[i][j], i-1<=k<j
16 */
17 dp()
18 {
19 int i, j, k, up, max, rt;
20 for(j=1; j<=v-f+1; j++)
21 table[1][j] = values[1][j];
22 for(i=2; i<=f; i++) {
23 up = v-f+i;
24 for(j=i; j<=up; j++) {
25 max = INF;
26 for(k=i-1; k<j; k++)
27 max = table[i-1][k] > max ? table[i-1][k] : max;
28 table[i][j] = max+values[i][j];
29 }
30 }
31 rt = INF;
32 for(j=f; j<=v; j++)
33 rt = table[f][j]>rt ? table[f][j] : rt;
34 return rt;
35 }
36
37 int
38 main(int argc, char **argv)
39 {
40 int i, j;
41 while(scanf("%d %d", &f, &v)!=EOF) {
42 for(i=1; i<=f; i++)
43 for(j=1; j<=v; j++)
44 scanf("%d", values[i]+j);
45 printf("%d\n", dp());
46 }
47 }