L. Elevator

watersail / 2024-11-09 / 原文

在证明了标记的添加必定伴随着标记的删除后，你可以放心地使用或运算更新标记，而不用担心标记的重叠问题

点击查看代码

#include <bits/stdc++.h>
using namespace std;
struct t1
{
	long long c,w,f;
}t[100005];
bool cmp(t1 a,t1 b)
{
	return a.f>b.f;
}
long long ans,k;
long long cur,n;
void solve(int i,long long l,bool f)
{
	if(i==n+1)
	{
		return;//边界，1~n都已处理完成 
	}
	if(l==1)
	{
		if(t[i].w==1)
		{
			cur=max(cur,t[i].f);
			ans=ans+cur;
			cur=0;
			t[i].c--;
			if(!t[i].c)
			{
				solve(i+1,k,f);
			}
			else
			{
				solve(i,k,f);
			}
		}
		else
		{
			ans=ans+cur;
			cur=0;
			solve(i,k,f=true);
		}
		return;
	}//保证以下的l至少为2 
	if(t[i].w==1&&f)
	{
		t[i].c--;
		f=false;
		if(!t[i].c)
		{
			solve(i+1,l,f);
			return;
		}
	}//处理f标记，若f标记未去除，则w必定为2 
	if(l/t[i].w>t[i].c)
	{
		cur=max(cur,t[i].f);
		solve(i+1,l-t[i].c*t[i].w,f);
	}//容量绰绰有余 
	else if(l/t[i].w==t[i].c)
	{
		cur=max(cur,t[i].f);
		ans=ans+cur;
		cur=0;
		solve(i+1,k,f|(l%t[i].w));
	}//容量刚好够 
	else
	{
		cur=max(cur,t[i].f);//至少能运载一个 
		ans=ans+cur;
		cur=0;
		t[i].c-=(l/t[i].w);
		ans=ans+t[i].c/(k/t[i].w)*t[i].f;
		t[i].c%=(k/t[i].w);
		if(t[i].c)
		{
			solve(i,k,f|(l%t[i].w));
		}
		else
		{
			solve(i+1,k,f|(l%t[i].w));
		}
	}//容量不够 
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n>>k;
		for(int i=1;i<=n;i++)
		{
			cin>>t[i].c>>t[i].w>>t[i].f;
		}
		sort(t+1,t+n+1,cmp);
		cur=ans=0;
		solve(1,k,false);//只有w=1才有可能产生标记，而每次w=1都会删除原来的标记 
		cout<<ans+cur<<"\n";
	}
	return 0;
}