题解 P4953 【[USACO02FEB] Cow Cycling 奶牛赛车】

· · 题解

这里给大家提供一个二维dp的做法。
观察到必有至少一种最优解，使得每头牛领头的时间都是是一整段。可以用反证法证明如下：

又观察到牛与牛之间没有区别。所以可以用 dp[i][j] 表示一头剩余体力为 i 的牛一连领头 j 圈最少要几分钟，枚举第一分钟速度 k 可得

dp[i][j] = \min \{ dp[i - k^2][j-k] + 1 \mid 1 \leq k \leq j,k^2 \leq i\}

边界条件：dp[0...E][0] = 0

再用 f[i][j] 表示还剩 i 头牛没 AFO 体力不支，还有 j 圈要骑，最少需要几分钟。枚举第一头牛领头圈数 k 可得

f[i][j] = \min\{f[i - 1][j - k] + dp[E - (D - j)][k] \mid 0 \leq k \leq j\}

边界条件：f[0][0] = 0, f[0][1...D] = \infty

最后的答案就是 f[n][D] 的值。

复杂度是 O(E^{1.5}D + nD^2)，本题中约为 10^5，可以加强数据可以轻松跑到最优解（2019 年 1 月及之前）。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>
#include <set>
//#define LOCAL
#define maxe 105
#define maxd 105
#define maxn 25
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n,E,D;
int dp[maxe][maxd],f[maxn][maxd];
int main(){
    #ifdef LOCAL
    freopen("sample.in","r",stdin);
    freopen("sample.out","w",stdout);
    #endif
    scanf("%d%d%d",&n,&E,&D);
    if(E < D){
        puts("0");
        return 0;
    }
    memset(dp,0x3f,sizeof(dp));
    for(int i=0;i<=E;i++) dp[i][0] = 0;
    for(int i=1;i<=E;i++){
        for(int j=1;j<=D;j++){
            for(int k=1;k <= j && k * k <= i;k++){
                dp[i][j] = min(dp[i][j],dp[i - k * k][j - k] + 1);
            }
        }
    }
    memset(f,0x3f,sizeof(f));
    f[0][0] = 0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=D;j++){
            int p = D - j;
            for(int k=0;k<=j;k++){
                f[i][j] = min(f[i][j],f[i - 1][j - k] + dp[E - p][k]);
            }
        }
    }
    printf("%d\n",f[n][D]);
    return 0;
}