Welcome to Leon's Blog  
日历
<2008年7月>
日一二三四五六
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789
统计
  • 随笔 - 30
  • 文章 - 0
  • 评论 - 51
  • 引用 - 0

导航

常用链接

留言簿(4)

随笔分类

随笔档案

ACM

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 
acm pku 1010 程序
       今天早上终于提交成功了！这道题做了有一个星期多了，老是找不到原因。今天在偶然间发现了，先将代码贴出来，还请大家指正！感谢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}

posted on 2008-07-01 09:56 Leon916 阅读(1921) 评论(4)  编辑 收藏 引用
评论:
  • # re: acm pku 1010 程序  企业即时通讯 Posted @ 2008-07-01 12:43
    哈哈，写的挺好的，加油哦。  回复  更多评论   

  • # re: acm pku 1010 程序[未登录]  Leon Posted @ 2008-07-01 14:34
    谢谢企业即时通讯，谢谢你的鼓励  回复  更多评论   

  • # re: acm pku 1010 程序  水 Posted @ 2008-07-01 15:23
    挺不错的，兄弟一直在做acm吗？  回复  更多评论   

  • # re: acm pku 1010 程序  qingzheng Posted @ 2010-07-06 19:02
    似乎没有用到动态规划  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © Leon916 Powered by: 博客园 模板提供：沪江博客