递推DP UVA 590 Always on the run-白红宇

递推DP UVA 590 Always on the run

阅读量：6734 次

发布时间：2019-06-25

本文共 1125 字，大约阅读时间需要 3 分钟。

题意：题意难懂，就是一个小偷在m天内从城市1飞到城市n最小花费，输入的是每个城市飞到其他城市的航班。

分析：dp[i][j] 表示小偷第i天在城市j的最小花费。状态转移方程：dp[i][j] = min (dp[i-1][k] + cost[k][j][t%day]) t表示在t天时k飞往j的飞机的花费

收获：

代码：

/************************************************* Author        :Running_Time* Created Time  :2015-8-29 14:07:43* File Name     :UVA_590.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;int dp[1010][12];int d[12][12];int cost[12][12][32];int main(void) { int n, m, cas = 0; while (scanf ("%d%d", &n, &m) == 2) { if (n == 0 && m == 0) break; for (int i=1; i<=n; ++i) { for (int j=1; j<=n; ++j) { if (i != j) { scanf ("%d", &d[i][j]); for (int k=0; k