問(wèn)題:
http://poj.org/problem?id=1010思路:
題目比較難理解，解題的話就是DFS
整整花了我一個(gè)晚上，終于AC了，(*^__^*) 嘻嘻……
雖然時(shí)間花了挺久，雖然自己的解法時(shí)間需要500+MS，雖然存在其他更優(yōu)的解法，雖然......，但還是相當(dāng)有成就感，完全是我自己寫(xiě)出來(lái)的
如果這題放在5個(gè)月之前，估計(jì)完全不知道怎么去寫(xiě)
在沒(méi)AC之前，我一直想著自己還是原來(lái)那么菜，現(xiàn)在，至少可以說(shuō)，比5個(gè)月之前的我已經(jīng)強(qiáng)了
繼續(xù)努力，F(xiàn)ighting...
代碼:
1 /* 388K 547MS */
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5 #define MAX_LEN 65 /* maximum number of different types of stamps */
6 #define UPPER 4 /* maximum number of stamps */
7 int types, stamps[MAX_LEN];
8 int request;
9 int maxdf, minusd, high, tie, exist, mark[MAX_LEN], ans[MAX_LEN];
10
11 int
12 compare(const void *arg1, const void *arg2)
13 {
14 return (*(int *)arg1)-(*(int *)arg2);
15 }
16
17 void
18 output()
19 {
20 int i, j;
21 if(!exist) {
22 printf("%d ---- none\n", request);
23 return;
24 }
25 printf("%d (%d): ", request, maxdf);
26 if(tie)
27 printf("tie\n");
28 else {
29 for(i=0; i<types; i++)
30 for(j=0; j<ans[i]; j++)
31 printf("%d ", stamps[i]);
32 printf("\n");
33 }
34 }
35
36 void
37 dfs(int remain, int index, int curdf, int curusd, int curhigh)
38 {
39 int i, flag = 0;
40 if(remain == 0) {
41 if(curdf < maxdf)
42 return;
43 /* satisfy the conditions: UPDATE */
44 if((curdf>maxdf) || (curdf==maxdf&&curusd<minusd) || (curdf==maxdf&&curusd==minusd&&curhigh>high)) {
45 maxdf = curdf;
46 minusd = curusd;
47 high = curhigh;
48 exist = 1;
49 tie = 0; /* remember reset 'tie' */
50 memcpy(ans, mark, sizeof(int)*MAX_LEN); /* copy the current best to 'ans' */
51 return;
52 }
53 /* TIE occurred */
54 if(curdf==maxdf && curusd==minusd && curhigh==high) {
55 tie = 1;
56 return;
57 }
58 return;
59 }
60 /* still exist several stamps unmarked */
61 for(i=index; i<types; i++) { /* Attention: i starts from 'index', which avoid duplicates such as '1 3' and '3 1' */
62 if(!mark[i] && stamps[i]<=remain && curusd+1<=UPPER) {
63 ++mark[i];
64 flag = 1;
65 dfs(remain-stamps[i], i+1, curdf+1, curusd+1, stamps[i]);
66 --mark[i];
67 }
68 }
69 /* all available stamps have been marked */
70 if(!flag) {
71 for(i=types-1; i>=0; i--) {
72 if(stamps[i]<=remain && curusd+1<=UPPER) {
73 ++mark[i];
74 dfs(remain-stamps[i], 0, curdf, curusd+1, curhigh);
75 --mark[i];
76 }
77 }
78 }
79 }
80
81 int
82 main(int argc, char **argv)
83 {
84 while(1) {
85 types = 0;
86 if(scanf("%d", &stamps[types]) == EOF)
87 break;
88 ++types;
89 while(scanf("%d", &stamps[types]) && stamps[types])
90 ++types;
91 qsort(stamps, types, sizeof(int), compare); /* ascent order */
92
93 while(scanf("%d", &request) && request) { /* each request */
94 maxdf = high = 0;
95 minusd = MAX_LEN+1;
96 exist = tie = 0;
97 memset(mark, 0, sizeof(mark));
98 dfs(request, 0, 0, 0, 0);
99 output();
100 }
101 }
102 return 0;
103 }