• 网志分类
  • » 查看所有日志 (45)
    » ACM (24)
    » 程序设计语言 (3)
    » 我的软件 (5)
    » 转贴 (12)
    » 被遗忘的角落 (1)
  • 站内搜索
  • 友情链接
  • » 我的歪酷 非非共享界
    » kuye
    » 开复学生网

    订阅 RSS

    歪酷博客

    0011513

    « 上一篇: 又是一道DP 下一篇: UVa 上ac的第50题 ... 庆祝一下 »
    kodder @ 2006-05-14 10:31

    /*
    * UVa 10465 Homer Simpson Algorithm DP...
    * 感觉这题很简单, 但是状态转移方程也想了挺长的时间。
    * 之前对dp的感觉就是状态转移方程很难设计, 现在决觉的dp和递推关系很密切
    * 自顶向下分析, 自底向上求解。
    * dp就是DP,写出来的代码就是短啊, 这也是我做dp的一个原因.我很懒的^-^
    */
    #include <stdio.h>
    #include <stdlib.h>
     
    #define MAX 10001
     
    struct arr {
           int cntb;
           int cnts;
    } Arr[MAX];
     
    int main(void)
    {
           int i, m, n, t, big, small;
           int a, b, x, y;
          
           while (scanf("%d %d %d", &m, &n, &t) == 3) {
                  big = m > n ? m : n;
                  small = m + n - big;
                  Arr[0].cntb = Arr[0].cnts = 0;
                  for (i = 1; i <= t; i++) {
                         if (i < small) {
                                Arr[i].cntb = Arr[i].cnts = 0;
                         } else if (i < big && i >= small) {
                                // we can only eat small one
                                Arr[i].cnts = Arr[i - small].cnts + 1;
                                Arr[i].cntb = Arr[i - small].cntb;
                         } else {
                                a = Arr[i - small].cnts + Arr[i - small].cntb;
                                x = i - small - (Arr[i - small].cnts*small + Arr[i - small].cntb*big);
                                b = Arr[i - big].cnts + Arr[i - big].cntb;
                                y = i - big - (Arr[i - big].cnts*small + Arr[i - big].cntb*big);
                                if (x < y || (x == y && a > b)) {
                                       // we must choice small...
                                       Arr[i].cnts = Arr[i - small].cnts + 1;
                                       Arr[i].cntb = Arr[i - small].cntb;
                                } else {
                                       // just choice big one...
                                       Arr[i].cnts = Arr[i - big].cnts;
                                       Arr[i].cntb = Arr[i - big].cntb + 1;
                                }
                         }
                  }
                  printf("%d", Arr[t].cnts + Arr[t].cntb);
                  if (t != Arr[t].cnts*small + Arr[t].cntb*big) {
                         printf(" %d", t - (Arr[t].cntb*big + Arr[t].cnts*small));
                  }
                  printf("\n");
           }
           return 0;
    }
     




    评论 / 个人网页 / 扔小纸条
    * 昵称

    已经注册过? 请登录

    新用户请先注册 以便能显示头像及追踪评论回复

    Email
    网址
    * 评论
    表情
     


     

    分类小组论坛
    杂谈 , 娱乐、八卦 , 文学、艺术 , 体育 , 旅游、同城 , 象牙塔 , 情感 , 时尚、生活 , 星座 , 科技

    请注意遵守中华人民共和国法律法规, 如威胁到本站生存, 将依法向有关部门报告, 同时本站的相关记录可能成为对您不利的证据.

    相关法律法规
    全国人大常委会关于维护互联网安全的决定
    中华人民共和国计算机信息系统安全保护条例
    中华人民共和国计算机信息网络国际联网管理暂行规定
    计算机信息网络国际联网安全保护管理办法
    计算机信息系统国际联网保密管理规定