数学考试——dp+滚动数组

数学考试 (nowcoder.com)

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+100;
typedef long long ll;
ll a[N],b[N],q[N],w[N];
ll dp[2][N];
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>q[i]>>w[i];
}
for(int i=1;i<=n;i++){
int now=i%2,last=1-now;//由于内存限制，并且每一层都由上一层的结果转移而来，因此用1,0分别表示当前层和上一层（滚动数组）
for(int j=0;j<=k;j++){//做完i题后才更改压力值
if(j-q[i]>=0)dp[now][j]=max(dp[now][j],dp[last][j-q[i]]+(j-q[i]<=b[i])*(j-q[i])*a[i]);//上一层p选择增加q[i]
if(j+w[i]<=k)dp[now][j]=max(dp[now][j],dp[last][j+w[i]]+(j+w[i]<=b[i])*(j+w[i])*a[i]);//上一层p选择减少w[i]
dp[now][j]=max(dp[now][j],dp[last][j]+(j<=b[i])*j*a[i]);//上一层p选择不变
}
}
ll ans=0;
for(int i=0;i<=k;i++)ans=max(ans,dp[n%2][i]);//n的奇偶决定最后一个数是0还是1,再将每个压力值下求最大
cout<<ans<<endl;
return 0;
}

最后

以上就是欣慰汉堡为你收集整理的数学考试——dp+滚动数组的全部内容，希望文章能够帮你解决数学考试——dp+滚动数组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。