自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:12:14，当前版本为作者最后更新于2019-10-03 00:42:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\color{#9400d3}T4.\ Doing\ Homework$

$\color{#9400d3}\text{题面}$

官方题解

我也不知道这个部分分给的有什么用

$Sol\ 1\ :\ 5-15\ pts$

爆搜，期望得分 $5-15\%$ （要看你怎么搜）

反正我也没写过爆搜

$Sol\ 2\ :\ 75-100\ pts$

（大多数应该能拿到 $100\%$，除非被卡空间）

一看题就应该知道 时间 $O(nk)$，空间 $O(k)$

如果没有时间的限制，那么这道题目就是完全背包

但有了时间怎么办 $qwq?$

不慌，将所有种类的作业按时间从大到小排

每次一种作业去更新 $dp$ 数组

再 对于每一个更新 求出最小（精力）花费

最后求出天数不就行了嘛 $awa$

记得用 $long\ long$ 啊！

上代码

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(3)
#define ll long long
ll read()//快读
{
	ll x=0,sign=1;char s=getchar();
	while(!isdigit(s))s=getchar();
	while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return x;
}
const ll N=5e3+2;
const ll INF=1e18;

struct homew{
	ll x,w,t,cos; 
}k[N];
bool cmp(homew a,homew b){return a.t>b.t;}//将作业按时间大小排序

ll min(ll a,ll b){return a<b?a:b;}//手写 min 函数
ll x,w,n,dp[N<<1];

void init()
{
	x=read(),w=read(),n=read();
	for(int i=1;i<=n;i++)
		k[i].x=read(),k[i].w=read(),k[i].t=read();//读入
	sort(k+1,k+n+1,cmp);//sort 
	memset(dp,0x3f,sizeof(dp));//dp 赋初值
	dp[0]=0;
}

void DP()
{
	for(int i=1;i<=n;i++){
		if(k[i].w>=w)//特判一下 w[i]>=w 的情况
			dp[w]=min(dp[w],k[i].x);
		else
			for(int j=k[i].w;j<=w+k[i].w;j++)//完全背包
				dp[j]=min(dp[j],dp[j-k[i].w]+k[i].x);
		k[i].cos=INF;//赋初值
		for(int j=w;j<=(w<<1);j++)
			k[i].cos=min(k[i].cos,dp[j]);//找出最小值
	}
}

void answer()
{
	for(int i=n;i>0;i--){//时间从小到大遍历
		ll cos=k[i].cos*(k[i].t-k[i+1].t);//总花费
		if(cos<=x)x-=cos;//有足够的精力
		else cout<<k[i+1].t+x/k[i].cos<<" "<<x%k[i].cos<<endl,exit(0);//否则输出并退出
	}
	cout<<k[1].t<<" "<<x;//特判天天能写完作业
}

int main()
{
	init();
	DP();
	answer();
	return 0;
}