1 条题解

  • 0
    @ 2026-5-7 18:48:13

    一种代码特别短的解法。

    考虑到 p p v v 都非常小,答案应该也不是很大。于是考虑枚举答案。

    设当前枚举到的答案为 t t,用 ft f_t 表示所需的时间。可以得到转移方程式

    ft=max(ftvi×p×i) f_t = \max (f_{t-v-i\times p}\times i)

    这样一直枚举,直到 ft f_t 大于 n n 时停止。

    最后测试了一下极限数据,最大也就十二万左右。

    代码如下 :

    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    int n,p,v;
    vector <int> f;
    int t;
    signed main(){
        cin>>n>>p>>v;
        f.push_back(1);
        while(f[t]<n)
        {
            f.push_back(f[t++]);
            for(int i=2;i<=(t-v)/p;++i)   f[t]=max(f[t],f[t-v-i*p]*i);
        }
        cout<<t<<endl;
        return 0;
    }
    
    • 1

    信息

    ID
    4012
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者