|
日歷
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 26 | 27 | 28 | 29 | 30 | 31 | 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 | 1 | 2 | 3 | 4 | 5 | 6 |
|
統計
- 隨筆 - 30
- 文章 - 0
- 評論 - 51
- 引用 - 0
導航
常用鏈接
留言簿(4)
隨筆分類
隨筆檔案
ACM
搜索
最新評論
閱讀排行榜
評論排行榜
|
今天早上終于提交成功了！ 這道題做了有一個星期多了，老是找不到原因。今天在偶然間發現了，先將代碼貼出來，還請大家指正！感謝steven和一個匿名網友的建議，謝謝你們！但是程序運行的時間還是過長，希望大家能夠幫助修改。
1 #include <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5
6int result[4];
7int reNumber, reCount, tie, reMax; //result是最終客戶的郵票種類，reCount是客戶郵票總個數，reNumber是客戶不同郵票的個數
8
9int GetNumber(int *stamp, int *customer, int *stampNumber, int *customerNumber) //獲取郵票 和 客戶信息。
10   {
11 int i, n,count[100]; // count在這里起到一個優化的作用。
12 n = 0;
13 (*stampNumber) = 0;
14 memset(count, 0 ,sizeof(int)*100);
15 while(1) //收集關于郵票的面值。
16  {
17 if(scanf("%d", &n) == EOF)
18 return -1;
19 if(n == 0)
20 break;
21 if(count[n]++ < 5)
22 stamp[(*stampNumber)++] = n;
23 }
24 //stampNumber--;
25 (*customerNumber) = 0;
26 while(1)
27 {
28 scanf("%d", &n); //收集關于客戶需要郵票的總面值數。
29 if(n == 0)
30 break;
31 customer[(*customerNumber)++] = n;
32 }
33 return 1;
34 }
35int NotSame(int *number,const int count, int *m,int *stamp) //求不同一組郵票類別的個數和郵票的最大面值。
36{
37 int i,j, c,s;
38 c = 0;
39 *m = stamp[number[0]];
40 for(i = 0; i < count; i++)
41 {
42 if( *m < stamp[number[i]]) //求最大面值的郵票
43 *m = stamp[number[i]];
44 s = 0;
45 for(j = 0; j < i; j++) //求不同面值郵票的個數
46 {
47 if(number[i] == number [j])
48 {
49 s = 1;
50 break;
51 }
52 }
53 if(0 == s)
54 c++;
55 }
56 return c;
57}
58
59
60void Divide(int sum, int *number, int *stamp,int n, int *count, int same,int start)
61{
62 int i;
63 int t;
64 if( *count > 4 )
65 return;
66 else if( sum == 0 && *count <= 4) //郵票個數《=4的時候且保存在數組number中的郵票面值=sum的時候。
67 {
68 same = NotSame(number, *count,&t, stamp);
69 if( same > reNumber || same == reNumber && reCount > *count || same == reNumber && reCount == *count && reMax < t )//根據不同的條件來判斷。
70 {
71 reMax = t;
72 reCount = *count;
73 reNumber = same;
74 for(i = 0; i < *count; i++)
75 result[i] = number[i];
76 tie = 0;
77 }
78 else if(same == reNumber && reCount == *count && reMax == t)//當郵票面值的最大值、郵票種類數，郵票個數相等時。
79 {
80 tie = 1;
81 }
82
83 return;
84 }
85 for(i = start; i < n; i++) //遞歸搜索
86 {
87 sum -= stamp[i];
88 if(sum >= 0)
89 {
90 number[(*count)++] = i;
91 Divide(sum, number, stamp, n, count,same,i);
92 (*count)--;
93 }
94 sum += stamp[i];
95 }
96}
97
98
99int main(int argc, char* argv[])
100{
101 int stamp[100], customer[100]; //stamp保存郵票的面值，customer保存客戶需要郵票的總面值。
102 int number[5]; //臨時數據，記錄滿足條件的臨時結果。此前提交一直WA的原因是number分配的空間太小了！
103 int count,stampNumber = -1, customerNumber = -1;//stampNumber是郵票的個數，customerNumber是客戶個數
104 int i,j;
105
106 do
107 {
108 memset(stamp, 0, 100*sizeof(int));
109 memset(customer, 0, 100*sizeof(int));
110 memset(number, 0 ,4);
111 if(GetNumber(stamp, customer, &stampNumber, &customerNumber) == -1)
112 break;
113 for(i = 0; i < customerNumber; i++)
114 {
115 reMax = -1; //對數據初始化。
116 memset(result, 0, 4);
117 reNumber = -1;
118 count=0;
119 tie = 0;
120 Divide(customer[i], number,stamp, stampNumber/**//*+1*/,&count, -1,0);
121 if(reNumber != -1) //打印。
122 {
123 if(tie == 0) //找到滿足條件的結果。
124 {
125 printf("%d (%d):", customer[i], reNumber);
126 for(j = 0; j < reCount; j++)
127 printf(" %d",stamp[result[j]]);
128 printf("\n");
129 }
130 else if( tie == 1) //存在郵票面值的最大值、郵票種類數，郵票個數相同的答案
131 {
132 printf("%d (%d): tie\n",customer[i], reNumber);
133 }
134 }
135 else //不滿足條件
136 {
137 printf("%d ---- none\n",customer[i]);
138 }
139 }
140 }while(1);
141 return 0;
142}
評論:
-
# re: acm pku 1010 程序
Posted @ 2008-07-01 12:43
哈哈，寫的挺好的，加油哦。 回復 更多評論
-
# re: acm pku 1010 程序[未登錄]
Posted @ 2008-07-01 14:34
謝謝企業即時通訊，謝謝你的鼓勵 回復 更多評論
-
# re: acm pku 1010 程序
Posted @ 2008-07-01 15:23
挺不錯的，兄弟一直在做acm嗎？ 回復 更多評論
-
# re: acm pku 1010 程序
Posted @ 2010-07-06 19:02
似乎沒有用到動態規劃 回復 更多評論
|