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

    订阅 RSS

    歪酷博客

    0011509

    « 上一篇: UVa 116 Undirectional TSP 下一篇: UVa 10465 Homer Simpson (DP) »
    kodder @ 2006-05-13 14:32

    // http://online-judge.uva.es/p/v104/10440.html
    #include <stdio.h>
    #include <stdlib.h>
    #include <limits.h>
    #include <string.h>
     
    #define MAX 1441
     
    int arv[MAX], f[MAX], road[MAX];
     
    int main(void)
    {
           int i, j, k, n, t, m, cc, ntrans;
          
           scanf("%d", &cc);
           while (cc--) {
                  scanf("%d %d %d", &n, &t, &m);
                  if (m == 0) {
                         printf("0 0\n");
                         continue;
                  }
                  for (i = 1; i <= m; i++) scanf("%d", &arv[i]);
                  memset(f, 0, sizeof(f));
                  memset(road, 0, sizeof(road));
                 
                  f[0] = -t;
                  arv[0] = 0;
                  for (i = 1; i <= m; i++) {
                         // 第i辆车可以选择n种方案
                         f[i] = INT_MAX;
                         for (j = i - n + 1; j <= i; j++) {
                                // choice car from j ... i inclusive...
                                if (j < 1) continue;
                                if (j == 1)
                                       k = arv[i] + t;
                                else {
                                       if ((k = f[j - 1] + t) < arv[i])
                                              k = arv[i];
                                       k += t;
                                }
                                if (f[i] > k) {
                                       f[i] = k;
                                       road[i] = j;
                                }
                         }
                  }
                  ntrans = 0;
                  i = m;
                  while (i > 0) {
                         i = road[i] - 1;
                         ntrans++;
                  }
                  printf("%d %d\n", f[m], ntrans);
           }
           return 0;
    }




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

    已经注册过? 请登录

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

    Email
    网址
    * 评论
    表情
     


     

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

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

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