数学考试

NC238810. 数学考试

描述

牛妹参加了 $2022$ 年普通高校全牛世界招生统一考试。数学试题太难，她决定复读。

为了在考试中取得更好的成绩，牛妹决定对数学进行特训。特训练习共 $n$ 道题，第 $i$ 题的难度为 $a_i$ ，分值为 $b_i$ 。为了更好提高自己的数学水平，牛妹决定按照题目顺序做题。
做题会对牛妹的压力指数 $P$ 产生影响。牛妹在长期磨练中养成了一颗大心脏，做完第 $i$ 题后，牛妹可以选择保持自己的压力指数 $P$ 不变、使 $P$ 增加 $Q_i$ 或使 $P$ 减少 $W_i$ 。压力指数上限为 $K$ ，下限为 $0$ 。如果 $P$ 增加 $Q_i$ 后大于 $K$ ，牛妹就不可以选择让自己的压力指数增加 $Q_i$ ；同理，如果 $P$ 减少 $W_i$ 后小于 $0$ ，牛妹就不可以选择让自己的压力指数减少 $W_i$ 。
牛妹相信压力可以转化为动力。当牛妹在压力为 $P$ 的状态下完成第 $i$ 题时，她一定可以做对这一题，并可以积累 $a_i \times P$ 的经验。但压力太大会反噬牛妹，当 $P > b_i$ 时，牛妹不能做对第 $i$ 题，无法积累任何经验。请注意，无论是否做对，都算作完成了第 $i$ 题，在做完后，才更改压力值。
牛妹想要知道，完成本次数学特训后，她最多可以积累多少经验。牛妹初始的压力值可以由牛妹在 $0 - K$ 范围内自由选定。
请注意，本题的空间限制较为特别，仅有 64MB。

输入描述

输入共  行。
输入的第一行为两个正整数 ，。
接下来  行，每行四个正整数，第  行分别为 。

输出描述

输出共一行，为牛妹可以积累经验的最大值。

示例1

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 173ms, 内存消耗: 664K, 提交时间: 2022-10-05 19:32:56

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;

ll dp[100020][2];
ll a,b,q,w;
ll n,k;
ll ans=0;

int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld%lld",&a,&b,&q,&w);
		int j;
		for(j=0;j<=k;j++)
		{
			dp[j][0]=dp[j][1];
			if(j<=b)
				dp[j][0]+=a*j;
		}
		for(j=0;j<=k;j++)
		{
			dp[j][1]=dp[j][0];
			if(j-q>=0)
				dp[j][1]=max(dp[j][1],dp[j-q][0]);
			if(j+w<=k)
				dp[j][1]=max(dp[j][1],dp[j+w][0]); 
		}
	}
	ll maxx=0;
	for(int i=0;i<=k;i++)
		maxx=max(maxx,dp[i][0]);
	printf("%lld\n",maxx); 
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 152ms, 内存消耗: 528K, 提交时间: 2022-10-03 08:08:40

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5;
int a,b,q,w,dp[N][2];
signed main()
{
	int n,k;
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld%lld",&a,&b,&q,&w);
		for(int j=0;j<=k;j++)
		{
			dp[j][0]=dp[j][1];
			if(j<=b) dp[j][0]+=a*j;
		}
		for(int j=0;j<=k;j++)
		{
			dp[j][1]=dp[j][0];
			if(j-q>=0) dp[j][1]=max(dp[j][1],dp[j-q][0]);
			if(j+w<=k) dp[j][1]=max(dp[j][1],dp[j+w][0]);
		}
	}
	int maxn=0;
	for(int j=0;j<=k;j++) maxn=max(maxn,dp[j][0]);
	printf("%lld",maxn);
	return 0;
}