解题报告 P1336 最佳课题选择

题目内容

P1336

一共写 n 篇论文，一共 m 个课题，对于第 i 个课题如果写 x 篇则需花费 A_i\times x^{B_i} 的时间，求最小时间

解题思路

泛化物品的背包，价值随着分给他的大小而变化。由于数据范围比较小，所以直接枚举第 i 个课题选择的数量 k 即可，转移方程：

f_{i,j}=\min(f_{i,j},f_{i-1,j-k}+A_i\times k^{B_i})

然后边界就是 f_{1,i}=A_1\times i^{B_1}，最后使用滚动数组优化一下即可

不开 long long 见祖宗

代码：

#include <cstdio>
#include <cctype>
#include <cstring>
typedef long long ll;

ll n,m,a[25],b[25],f[205];

inline ll read()
{
    char c = getchar();
    ll s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline ll min(ll a,ll b)
{
    return a<b?a:b;
}

inline ll ksm(ll base,ll p)//写了个快速幂
{
    ll ans=1;
    for(;p;p>>=1)
    {
        if(p&1)
            ans*=base;
        base*=base;
    }
    return ans;
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
        a[i]=read(),b[i]=read();
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++)
        f[i]=a[1]*ksm(i,b[1]);
    //边界
    for(int i=2;i<=m;i++)
        for(int j=n;j>=0;j--)
            for(int k=0;k<=j;k++)
                f[j]=min(f[j],f[j-k]+a[i]*ksm(k,b[i]));//进行转移
    printf("%lld\n",f[n]);
    return 0;
}