UVA1025---A Spy in the Metro(简单dp) - c++编程基础

TOP

UVA1025---A Spy in the Metro(简单dp)

2015-11-21 01:01:10 来源: 作者: 【大中小】浏览:1次

dp[i][j] 表示时刻i,在车站j,等待的最少时间
有3种方案:
等一分钟
往左搭车
往右搭车

/*************************************************************************
    > File Name: uva1025.cpp
    > Author: ALex
    > Mail: zchao1995@gmail.com 
    > Created Time: 2015年05月25日 星期一 19时05分09秒
 ************************************************************************/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              #include 
              
                #include 
               
                 #include 
                
                  using namespace std; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair 
                 
                   PLL; int dp[220][55]; int t_use[55]; vector 
                  
                    go[220][55]; int main() { int n, T, icase = 1, times; while (~scanf("%d", &n), n) { scanf("%d", &T); int m1, m2; // m1 : L to R, m2 : R to L for (int i = 1; i <= n - 1; ++i) { scanf("%d", &t_use[i]); } for (int i = 0; i <= T; ++i) { for (int j = 1; j <= n; ++j) { go[i][j].clear(); // time = i, station = j } } scanf("%d", &m1); for (int i = 1; i <= m1; ++i) { scanf("%d", ×); int t = times; if (t > T) { continue; } go[t][1].push_back(i); for (int j = 1; j <= n - 1; ++j) { t += t_use[j]; if (t > T) { break; } go[t][j + 1].push_back(i); } } scanf("%d", &m2); for (int i = 1; i <= m2; ++i) { scanf("%d", ×); int t = times; if (t > T) { continue; } go[t][n].push_back(i + m1); for (int j = n - 1; j >= 1; --j) { t += t_use[j]; if (t > T) { break; } go[t][j].push_back(i + m1); } } for (int i = 0; i <= T; ++i) { for (int j = 1; j <= n; ++j) { dp[i][j] = inf; } } dp[0][1] = 0; for (int i = 0; i < T; ++i) { for (int j = 1; j <= n; ++j) { if (dp[i][j] == inf) { continue; } int size = go[i][j].size(); dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1); for (int k = 0; k < size; ++k) { int u = go[i][j][k]; if (u <= m1 && j < n) { if (i + t_use[j] <= T) { dp[i + t_use[j]][j + 1] = min(dp[i + t_use[j]][j + 1], dp[i][j]); } } else if (j > 1 && u > m1) { if (i + t_use[j - 1] <= T) { dp[i + t_use[j - 1]][j - 1] = min(dp[i + t_use[j - 1]][j - 1], dp[i][j]); } } } } } int ans = inf; for (int i = 0; i <= T; ++i) { if (dp[i][n] == inf) { continue; } ans = min(ans, dp[i][n] + T - i); } if (ans == inf) { printf("Case Number %d: impossible\n", icase++); } else { printf("Case Number %d: %d\n", icase++, ans); } } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU ACM 1272 小希的迷宫	下一篇：线段树区间更新，区间统计 poj 27..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: