問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1179思路:
這題輸在了對原題目的理解和分析上，沒能成功地走出第一步:
將原題解析成對于表達式的求解
把缺了一條邊的多邊形展開成直線就是一個表達式
注意：為了求乘法，必須同時保存最大值和最小值
f[i][j]記錄表達式中從頂點i到頂點j這段子表達式的值
動態(tài)規(guī)劃的思想類似于矩陣連乘
參考:
http://hi.baidu.com/xiehuixb/blog/item/575ec81e221466c1a786699e.html代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 51
5 #define INF 9223372036854775807LL
6 #define maximal(a, b) ((a)>(b) ? (a) : (b))
7 #define minimal(a, b) ((a)<(b) ? (a) : (b))
8 char operand[MAX_LEN][2];
9 int operators[MAX_LEN];
10 int n, ans_len, ans[MAX_LEN];
11 long long int rt, max[MAX_LEN][MAX_LEN], min[MAX_LEN][MAX_LEN];
12
13 /*
14 * when it comes to: '+'
15 * max[i][j] = maximal(max[i][k] + max[k+1][j])
16 * min[i][j] = minimal(min[i][k] + min[k+1][j])
17 *
18 * when it comes to: '*'
19 * max[i][j] = maximal(max[i][k]*max[k+1][j], max[i][k]*min[k+1][j], min[i][k]*max[k+1][j], min[i][k]*min[k+1][j])
20 * min[i][j] = minimal(max[i][k]*max[k+1][j], max[i][k]*min[k+1][j], min[i][k]*max[k+1][j], min[i][k]*min[k+1][j])
21 *
22 * i<=k<j
23 */
24 void
25 solve(char *opd, int *ops, int del_edge)
26 {
27 int i, j, k, len;
28 for(i=1; i<=n; i++)
29 max[i][i] = min[i][i] = ops[i];
30 for(len=2; len<=n; len++) {
31 for(i=1; i<=n-len+1; i++) {
32 j = i+len-1;
33 max[i][j] = -INF;
34 min[i][j] = INF;
35 for(k=i; k<j; k++) {
36 if(opd[k] == 't') {
37 max[i][j] = maximal(max[i][j], max[i][k]+max[k+1][j]);
38 min[i][j] = minimal(min[i][j], min[i][k]+min[k+1][j]);
39 } else { /* opd[k] == 'x' */
40 max[i][j] = maximal(max[i][j], max[i][k]*max[k+1][j]);
41 max[i][j] = maximal(max[i][j], max[i][k]*min[k+1][j]);
42 max[i][j] = maximal(max[i][j], min[i][k]*max[k+1][j]);
43 max[i][j] = maximal(max[i][j], min[i][k]*min[k+1][j]);
44
45 min[i][j] = minimal(min[i][j], max[i][k]*max[k+1][j]);
46 min[i][j] = minimal(min[i][j], max[i][k]*min[k+1][j]);
47 min[i][j] = minimal(min[i][j], min[i][k]*max[k+1][j]);
48 min[i][j] = minimal(min[i][j], min[i][k]*min[k+1][j]);
49 }
50 }
51 }
52 }
53 if(max[1][n] >= rt) {
54 if(max[1][n] == rt)
55 ans[ans_len++] = del_edge;
56 else {
57 rt = max[1][n];
58 ans_len = 0;
59 ans[ans_len++] = del_edge;
60 }
61 }
62 }
63
64 int
65 main(int argc, char **argv)
66 {
67 int i, j, k;
68 char tmpopd[MAX_LEN];
69 int tmpops[MAX_LEN];
70 while(scanf("%d", &n) != EOF) {
71 for(i=1; i<=n; i++)
72 scanf("%s%d", operand[i], operators+i);
73 rt = -INF;
74 ans_len = 0;
75 for(i=1; i<=n; i++) {
76 for(j=i%n+1, k=1; j!=i; j=j%n+1, k++)
77 tmpopd[k] = operand[j][0];
78 tmpopd[k] = '\0';
79 tmpops[1] = operators[i];
80 for(j=i%n+1, k=2; j!=i; j=j%n+1, k++)
81 tmpops[k] = operators[j];
82 solve(tmpopd, tmpops, i);
83 }
84 printf("%lld\n", rt);
85 for(i=0; i<ans_len; i++)
86 printf("%d ", ans[i]);
87 printf("\n");
88 }
89 }