题解：P4399 [JSOI2008] Blue Mary的职员分配
Heart_Of_Iron_4
·
·
题解
这道题是 dp 毫无疑问，但我提供一个压成 3 维的想法。\
因为每个员工每天能搞到 x 个钱，y 个声誉，所以 y 个声誉 =x 个钱。\
所以我们令 a=a+\lceil a\div y \rceil \times x，\
（\lceil \rceil 是上取整函数），这样只算钱就行了。\
指现在有 $i$ 个职员，下次时刻为 $j$ 时能发广告，有 $k$ 个钱，时刻为 $l$。
转移方程如下：
```cpp
//新招收员工
dp[i+1][dp[i][j][k]+3][k-z+3*i*x]=min(dp[i][j][k]+3)
//原来的员工赚了一天钱
dp[i][j][k+i*x]=min(dp[i][j][k]+1)
```
最后统计一下 钱比 $a$ 多的状态 的时刻最小值就行了 qaq。\
其他细节在代码里。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define getmin(qwe,wer) qwe>wer?qwe=wer:114514
int dp[110][110][610];
int n,x,y,z,a,b,ans;
signed main()
{
memset(dp,0x3f3f3f3f,sizeof dp);
cin>>n>>x>>y>>z>>a>>b;
a+=ceil(b*1.0/y)*x;
//cout<<a<<endl;
dp[n][0][0]=0;
for(int i=n;i<=n+15;++i)
{
for(int j=0;j<=40;++j)
{
for(int k=0;k<=a+40;++k)
{
if(dp[i][j][k]>=4557430888798830399)continue;
//printf("%lld %lld %lld %lld\n",i,j,k,dp[i][j][k]);
if(dp[i][j][k]<j)continue;
if(dp[i][j][k]>=j&&k>=z)
{
getmin(dp[i+1][dp[i][j][k]+3][k-z+3*i*x],dp[i][j][k]+3);
}
getmin(dp[i][j][k+i*x],dp[i][j][k]+1);
}
}
}
ans=INT_MAX;
for(int i=a;i<=a+40;++i)
{
for(int j=n;j<=n+15;++j)
{
for(int k=0;k<=40;++k)
{
// if(dp[j][k][i]<ans)cout<<j<<" "<<k<<" "<<i<<" "<<dp[j][k][i]<<endl;
ans=min(dp[j][k][i],ans);
}
}
}
cout<<ans<<endl;
return 0;
}
```