炒鸡矿工

小 $\text{D}$ 最近在玩一款叫做炒鸡矿工的游戏。这个游戏的玩法建立在一个挖矿系统上。
我们认为游戏从第 $\text 0$ 分钟开始，每过 $\mathop p$ 分钟，炒鸡矿工可以完成一次挖矿，每次可以挖重量为 $\mathop c$ 的金矿，准确的说，在一次挖矿中，小 $\text{D}$ 会在第 $\mathop p$ 分钟末收获重量为 $\mathop c$ 的金矿。炒鸡矿工在开局后会不断地重复挖矿操作，不能休息。
金矿可以储存或用于升级挖矿系统。
开局时，挖矿系统的等级为 $\text 1$ 级。挖矿系统最多升到 $n+\text 1$ 级。升级操作不消耗时间，但只能在一次挖矿开始前进行。每次升级会从第 $\mathop i$ 级升级到第 $i+1(1\le i \le n)$ 级，需要花费重量为 $w_i$ 的金矿，可以使每次挖矿的重量增加 $v_i$ ，使每次挖矿的时间变成 $s_i$ 。由于升级不消耗时间，小 $\text{D}$ 可以在一瞬间多次升级。
开局时，小 $\text{D}$ 拥有重量为 $\mathop m$ 的金矿。他想知道，在开局后恰好 $\mathop t$ 分钟时，他最多能拥有的金矿重量是多少。

输入共 $\text 4$ 行（或 $\text 1$ 行）。
第一行包含 $\text 5$ 个非负整数 $p,c,n,m,t(0\le n \le 5\cdot 10^3)$ 。
第二行包含 $\mathop n$ 个非负整数，第 $\mathop i$ 个数表示 $w_i$ 。
第三行包含 $\mathop n$ 个非负整数，第 $\mathop i$ 个数表示 $v_i(0\le m,c,w_i,v_i\le 10^9)$ 。

第四行包含 $\mathop n$ 个正整数，第 $\mathop i$ 个数表示 $s_i(1\le p,s_i,t\le 5\cdot 10^3)$ 。

若 $n=\text 0$ ，则只有第一行。

#include<bits/stdc++.h> using namespace std; int w[5005],s[5005]; long long ans=0,DP[5005][5005],v[5005]; int main() { int i,j,p,c,n,m,t; scanf("%d%d%d%d%d",&p,&c,&n,&m,&t); memset(DP,-0x3f,sizeof(DP)); s[0]=p,v[0]=c,DP[0][0]=m; for(i=1;i<=n;i++)scanf("%d",&w[i]); for(i=1;i<=n;i++)scanf("%lld",&v[i]),v[i]+=v[i-1]; for(i=1;i<=n;i++)scanf("%d",&s[i]); for(i=0;i<=n;i++) { for(j=0;j<=t;j++) { if(j)DP[i][j]=max(DP[i][j],DP[i][j-1]); if(j>=s[i])DP[i][j]=max(DP[i][j],DP[i][j-s[i]]+v[i]); if(i&&DP[i-1][j]>=w[i])DP[i][j]=max(DP[i][j],DP[i-1][j]-w[i]); } } for(i=0;i<=n;i++)ans=max(ans,DP[i][t]); printf("%lld\n",ans); }

详情