数学考试 (nowcoder.com)
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#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+滚动数组内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复