专栏文章

P10981 任务安排 4.2【暂无数据】 题解

P10981题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipjycm2
此快照首次捕获于
2025/12/03 13:14
3 个月前
此快照最后确认于
2025/12/03 13:14
3 个月前
查看原文

前置知识

解法

luogu P10979 任务安排 2 得到基本转移方程为 fi=minj=0i1{fj+sumti(sumcisumcj)+s(sumcnsumcj)}f_{i}=\min\limits_{j=0}^{i-1} \{ f_{j}+sumt_{i}(sumc_{i}-sumc_{j})+s(sumc_{n}-sumc_{j}) \},删去状态转移方程中的 min\min,将 fjf_{j}sumcjsumc_{j} 看作变量,在以 sumcjsumc_{j} 为横坐标,以 fjf_{j} 为纵坐标的平面直角坐标系中可以得到直线 y=kx+by=kx+b,其中 {x=sumcjy=fjk=s+sumtib=fisumti×sumcis×sumcn\begin{cases} x=sumc_{j} \\ y=f_{j} \\ k=s+sumt_{i} \\ b=f_{i}-sumt_{i} \times sumc_{i}-s \times sumc_{n} \end{cases}
本题中因横坐标 xx 和斜率 kk 都不单调递增,可以使用 CDQ 分治优化转移,具体写法同 luogu P4655 [CEOI2017] Building Bridges
因为暂时没有数据,所以不保证代码一定正确。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
ll f[300010],t[300010],c[300010],k[300010],p[300010],tmp[300010],n,s;
deque<ll>q;
bool cmpk(ll a,ll b)
{
	return k[a]<k[b];
}
ll x(ll i)
{
	return c[i];
}
ll y(ll i)
{
	return f[i];
}
bool cmpx(ll a,ll b)
{
	return (x(a)==x(b))?(y(a)<y(b)):(x(a)<x(b));
}
void cdq(ll l,ll r)
{
	if(l==r)  return;
	ll mid=(l+r)/2;
	for(ll i=l,x=l,y=mid+1;i<=r;i++)
	{
		if(p[i]<=mid)
		{
			tmp[x]=p[i];  x++;
		}
		else
		{
			tmp[y]=p[i];  y++;
		}
	}
	for(ll i=l;i<=r;i++)  p[i]=tmp[i];
	cdq(l,mid);
	q.clear();
	for(ll i=l;i<=mid;i++)
	{
		while(q.size()>=2&&(y(q.back())-y(q[q.size()-2]))*(x(p[i])-x(q.back()))>=
							(y(p[i])-y(q.back()))*(x(q.back())-x(q[q.size()-2])))
			q.pop_back();
		q.push_back(p[i]);
	}
	for(ll i=mid+1;i<=r;i++)
	{
		while(q.size()>=2&&(y(q[1])-y(q.front()))<=k[p[i]]*(x(q[1])-x(q.front())))
			q.pop_front();
		f[p[i]]=min(f[p[i]],f[q.front()]+t[p[i]]*(c[p[i]]-c[q.front()])+s*(c[n]-c[q.front()]));
	}
	cdq(mid+1,r);
	sort(p+l,p+r+1,cmpx);
}
int main()
{
// #define Isaac
#ifdef Isaac
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	cin>>n>>s;
	for(ll i=1;i<=n;i++)
	{
		cin>>t[i]>>c[i];  p[i]=i;
		t[i]+=t[i-1];  c[i]+=c[i-1];  k[i]=t[i]+s;
	}
	for(ll i=1;i<=n;i++)  f[i]=t[i]*c[i]+s*c[n];
	sort(p+1,p+1+n,cmpk);  cdq(1,n);
	cout<<f[n]<<endl;
	return 0;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...