POJ [USACO] Cow Cycling

71 阅读 0 评论 47 点赞

我是靠谱客的博主超帅芒果，最近开发中收集的这篇文章主要介绍POJ [USACO] Cow Cycling，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

The cow bicycling team consists of N (1 <= N <= 20) cyclists. They wish to determine a race strategy which will get one of them across the finish line as fast as possible.

Like everyone else, cows race bicycles in packs because that’s the most efficient way to beat the wind. While travelling at x laps/minute (x is always an integer), the head of the pack expends x*x energy/minute while the rest of pack drafts behind him using only x energy/minute. Switching leaders requires no time though can only happen after an integer number of minutes. Of course, cows can drop out of the race at any time.

The cows have entered a race D (1 <= D <= 100) laps long. Each cow has the same initial energy, E (1 <= E <= 100).

What is the fastest possible finishing time? Only one cow has to cross the line. The finish time is an integer. Overshooting the line during some minute is no different than barely reaching it at the beginning of the next minute (though the cow must have the energy left to cycle the entire minute). N, D, and E are integers.
Input

A single line with three integers: N, E, and D
Output

A single line with the integer that is the fastest possible finishing time for the fastest possible cow. Output 0 if the cows are not strong enough to finish the race.
Sample Input

3 30 20
Sample Output

7
Hint

[as shown in this chart:

                            leader E

               pack  total used this

time  leader  speed   dist   minute

  1      1      5       5      25

  2      1      2       7       4

  3      2*     4      11      16

  4      2      2      13       4

  5      3*     3      16       9

  6      3      2      18       4

  7      3      2      20       4

* = leader switch

译：

大意是问题：有n只奶牛进行自行车环跑，如果奶牛一分钟要跑x圈，则领跑者消耗x * x体力，后面跟跑的消耗x体力。现在给出N头奶牛的数目N，每头奶牛原先所具有的能量E，需要环跑的圈数D。只要有一只奶牛先达到D圈，就算完成环跑，
问奶牛能否完成环跑，如果不能，输出0。否则，输出环跑的最短时间。

minT[i][j][k] 表示 i 只体力为 j 的奶牛走 k 所需的最小时间
则 minT[i][j][k] = min{minT[i][j][k], minT[i-1][j-e][k-e] + minT[1][j][e]} for 1 <= e <= k and j ，表示先以速度 e 走一分钟
minT[1][j][k] = min{minT[1][j][k], minT[1][j - e * e][k - e] + 1} for 1 <= e * e <= j and e <= k
剩下只有初始化的问题了

#include<cstdio>
#include<iostream>
#define inf 99999999
using namespace std;
int f[30][110][110];
int main () {
    int n,e,d;
    cin>>n>>e>>d;
    f[1][0][0]=0;
    for(int i=1;i<=e;i++) f[1][i][0]=0;
    for(int i=1;i<=d;i++) f[1][0][i]=inf;
    for(int i=1;i<=e;i++) 
      for(int j=1;j<=d;j++) {
        f[1][i][j]=inf;
        for(int k=1;k*k<=i&&k<=j;k++) {
            f[1][i][j]=min(f[1][i][j],f[1][i-k*k][j-k]+1);
        }
      }
    for(int i=2;i<=n;i++)
      for(int j=1;j<=e;j++)
        for(int k=1;k<=d;k++) {
            f[i][j][k]=inf;
            for(int o=1;o<=j&&o<=k;o++) 
              f[i][j][k]=min(f[i][j][k],f[i-1][j-o][k-o]+f[1][j][o]);
        }
    if(f[n][e][d]>inf) cout<<"0"<<endl;
    else cout<<f[n][e][d]<<endl;
    return 0;
}