HDU 1494 跑跑卡丁车

2014-07-16 来源: AOQNRMGYXLMV 发布在  http://www.cnblogs.com/AOQNRMGYXLMV/p/3847867.html

很无爱的一道题。

题解都看得一知半解的。

acm之家的题解,留着以后慢慢体会:

把这题转化为背包模型,每个%20能量算一个单位,最多有15个,如果大于5个有一个加速卡,如果大于10个有2个加速卡,如果等于16则边为10,2个满时清0.15就是背包的最多容量,正常跑算一个物品,权值(这里不说重量有负值)为1,价值为ai,加速也算一个物品,权值为-5,价值为bi,每次都必须选一个物品,问最后获得得最少价值。恩,有点牵强,但只要转化好理解些。

那么状态转移方程为:dp[i+1][j+1] = min(dp[i][j]+a[i],dp[i+1][j+1]);  (dp[i][j]表示跑了i个赛道能量为j时最少的耗时,a[i]为正常跑的时间,和背包的转移方程很像吧)

dp[i+1][j-5] = min(dp[i][j]+b[i],dp[i+1][j-5];

 //#define LOCAL
 #include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <algorithm>
 using namespace std;

  + ;
 const int INF = 0xffffff0;
 ];
 int a[maxn], b[maxn];

 int main(void)
 {
     #ifdef LOCAL
         freopen("1494in.txt", "r", stdin);
     #endif

     int L, N;
     )
     {
         int tot = L * N;
         int i;
         ; i < L; ++i)
             scanf("%d", &a[i]);
         ; i < L; ++i)
             scanf("%d", &b[i]);
         for(i = L; i < tot; ++i)
         {
             a[i] = a[i % L];
             b[i] = b[i % L];
         }

         ; i <= tot; ++i)
             ; j <= ; ++j)
                 dp[i][j] = INF;
         dp[][] = a[];

         ; i < tot; ++i)
             ; j < ; ++j)
             {
                 ;
                 )
                     k = ;
                 dp[i+][k] = min(dp[i][j] + a[i], dp[i+][k]);
                 )
                     dp[i+][j-] = min(dp[i][j] + b[i], dp[i+][j-]);
             }

         int ans = INF;
         ; i < ; ++i)
             ans = min(ans, dp[tot][i]);
         printf("%d\n", ans);
     }

     ;
 }

代码君

相关文章