|
日历
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 29 | 30 | 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 | 1 | 2 | | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|
统计
- 随笔 - 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
似乎没有用到动态规划 回复 更多评论
|