P4953 题解

qwer6 · 2025-01-25 08:48:00 · 题解

数据范围十分小，我们不妨直接考虑记忆化解决。
我们可以简单判断领队就是个一次性用品，只要从领队的位置上退下来，我们就不再考虑这只奶牛是否可以到达终点了。
所以我们记录三个参数，表示现在是第 p 头奶牛当领队（前面的奶牛已经被扔掉了），领队的奶牛还剩 rem 体力，以及现在跑了 now 圈。
决策就是这一分钟跑几圈，注意要保证领队可以跑完，也就说最多可以跑 \sqrt {rem} 圈，总状态数 n\times m\times s，每一次转移都是 \sqrt m 的，所以最后的时间复杂度为 O(nms\sqrt m)，显然可以通过，并且代码简短无比。

#include<bits/stdc++.h>
#define Nxt puts("")
#define Spa putchar(32)
#define Pline puts("------------------------------")
namespace FastIO{
    int write_top,read_f,read_x;
    char read_char;
    int write_st[20];
    inline int read(int &a){
        read_char=getchar();
        read_f=1;
        a=0;
        while(!isdigit(read_char)){
            if(read_char=='-')read_f=-1;
            read_char=getchar();
        }
        while(isdigit(read_char)){
            a=(a<<1)+(a<<3)+(read_char^48);
            read_char=getchar();
        }
        return a=a*read_f;
    }
    inline int read(){
        read_char=getchar();
        read_f=1;
        read_x=0;
        while(!isdigit(read_char)){
            if(read_char=='-')read_f=-1;
            read_char=getchar();
        }
        while(isdigit(read_char)){
            read_x=(read_x<<1)+(read_x<<3)+(read_char^48);
            read_char=getchar();
        }
        return read_x*read_f;
    }
    inline void write(int x){
        if(x<0)putchar('-'),x=-x;
        write_top=0;
        do{
           write_st[++write_top]=x%10;
           x/=10;
        }while(x);
        while(write_top)putchar(write_st[write_top--]+'0');
        return ;
    }
    inline void tomax(int &a,int b){
        if(a<b)a=b;
        return ;
    }
    inline void tomin(int &a,int b){
        if(a>b)a=b;
        return ;
    }
}
using namespace FastIO;
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,s;
int dp[25][105][105];
bool vis[25][105][105];
int dfs(int p,int now,int rem){
    if(now>=s)return 0;
    if(!rem)return inf;
    if(p>n)return inf;
    if(vis[p][now][rem])return dp[p][now][rem];
    vis[p][now][rem]=1;
    int res=inf;
    for(int i=1;i*i<=rem;i++){//枚举这一分钟要跑几圈 
        tomin(res,dfs(p,now+i,rem-i*i)+1);//不换领队
        tomin(res,dfs(p+1,now+i,m-now-i)+1);
    }
    return dp[p][now][rem]=res;
} 
signed main(){
    read(n),read(m),read(s);
    dfs(1,0,m);
    write(dp[1][0][m]);
}