题解 CF922E 【Birds】
ChthollyTree
2019-07-13 23:07:18
我怕不是数据结构学傻了qwq，就这题也能写过数据结构优化dp
dp题
$f[i][j]$表示到第$i$棵树，召唤了$j$只鸟所剩下的能量最大值
那么我们可以很容易得到方程
$f[i][j] = max(f[i-1][k] -(j-k)*cost[i])+X(j-c[i]<=k<=j)$
这时候直接暴力的话会TLE
但是我们可以用st表优化
$f[i][j] = max(f[i-1][k] + k*cost[i]-j*cost[i])+X$
$ = max(f[i-1][k] + k*cost[i])-j*cost[i]+X$
所以我们用st表维护$f[i-1][k] + k*cost[i]$的区间最大值就行了qwq
转移的时候询问$[j-c[i],j]$的最大值即可
这样写可能常数有点大（我的代码最慢接近800ms）
```
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 1005
#define MAXC 10005
#define max(x,y) (x)>(y)?(x):(y)
const int INF = (int)0x3f3f3f3f*(int)0x3f3f3f3f;
int n,W,B,X,C;
int c[MAXN];
int f[MAXN][MAXC],g[MAXN][MAXC];
int s[MAXC][20];
int cost[MAXN];
inline void jianbiao(int ii)
{
for(int i = 0; i <= C; i ++)
s[i][0] = f[ii][i] + cost[ii+1]*i;
for(int j = 1; j <= 17; j ++)
for(int i = 0; i+(1<<j) <= C; i ++)
{
s[i][j] = max(s[i][j-1],s[i+(1<<(j-1))][j-1]);
}
}
inline int rmq(int l,int r)
{
if(l < 0) l = 0;
int o = log2(r-l+1);
return max(s[l][o],s[r-(1<<o)+1][o]);
}
void rd()
{
cin >> n >> W >> B >> X;
for(int i = 1; i <= n; i ++)
{
cin >> c[i];
C += c[i];
}
for(int i = 1; i <= n; i ++)
cin >> cost[i];
}
signed main()
{
rd();
f[0][0] = W;
g[0][0] = W;
for(int i = 1; i <= C; i ++) {
f[0][i] = -INF;
g[0][i] = -INF;
}
jianbiao(0);
for(int i = 1; i <= n; i ++) {
for(int j = 0; j <= C; j ++) {
f[i][j] = rmq(j-c[i],j) - j*cost[i] + X;
if(f[i][j] < X) f[i][j] = -INF;
if(f[i][j] > W+j*B) f[i][j] = W+j*B;
}
jianbiao(i);
}
int ans = 0;
for(int i = 0; i <= C; i ++)
if(f[n][i] >= 0) ans = i;
cout<<ans;
return 0;
}
```