P4953 [USACO02FEB] Cow Cycling

内拉组里 · 2025-01-25 09:57:47 · 题解

水紫，最多只有绿的难度。

Thoughts：

这种奶牛 dp 应该很容易看出来。

令 dp[i][j][k] 表示还剩 i 头奶牛在玩，领队的奶牛还有 j 格体力，

其余的最多还有 k 格体力，最小时间。

初始状态 dp[n][e][e] = 0 ，其余 dp[i][j][k] = \infin 。

决策点就是领队换与不换，一个显而易见的策略就是每次让领队跑死再换掉，

若最后一头奶牛都没有了，那就无法到达终点。话说好像没有这个点。

否则除领队以外其他的奶牛在最后一分钟冲刺时还有 e - d 格体力，因为没当过领队。

即 ans = \max \{ dp[i][j][e - d] \} 。

转移的话填表有点难写，所以采用刷表。

枚举速度 x 。

若更换领队，则有 dp[i][j - x^2][k - x] \le dp[i][j][k] + 1 。

若不换领队，则有 dp[i - 1][k - x^2][k - x] \le dp[i][j][k] + 1 。

转移的时候注意一下下标越界问题即可。

Analyses：

总时间复杂度 \Theta (NE^2 \sqrt{E}) 。

总空间复杂度 \Theta (NE^2) 。

Code：

/* reference : @Luogu.ZZJ__ (118248) */
/* strategy : lead in turn and then drop out */
#include    <iostream>
#include    <cstring>
using namespace std;
constexpr int inf = 0x3f3f3f3f;
constexpr int maxn = 24;
constexpr int maxe = 104;

int n, e, d;
int dp[maxn][maxe][maxe];
/* dp[i][j][k] means the minimal time when are only [i] cows,the leader has [j] power left,while others have [k] */

signed main (void)
{
    cin >> n >> e >> d;
    memset (dp, 0x3f, sizeof dp);
    dp[n][e][e] = 0;
    int ans = inf;
    for (int i = n; i; i--)
    {
        for (int j = e; ~j; j--)
        {
            for (int k = e; ~k; k--)
            {
                for (int x = 1; x <= 10; x++)
                {
                    if (j >= x * x && k >= x) dp[i][j - x * x][k - x] = min (dp[i][j - x * x][k - x], dp[i][j][k] + 1); /* keep on leading */
                    if (k >= x * x) dp[i - 1][k - x * x][k - x] = min (dp[i - 1][k - x * x][k - x], dp[i][j][k] + 1);   /* handover the position of leader */
                }
            }
            ans = min (ans, dp[i][j][e - d]);
        }
    }
    cout << ans << endl;
    return 0;
}