【TIOJ 1921】吐鈔機2

原題連結：https://tioj.ck.tp.edu.tw/problems/1921

似乎很久沒發文了……
最近有點忙加上最近寫的題目很多不是裸題就是看解答發現自己低能沒想到解(?

可以很輕易的列出DP式
若$\color{white}{\space dp[i]\space}$表示買進第$\color{white}{\space i\space}$台機器時，擁有的最多錢數
則
$\color{white}{\space dp[i]=max\{dp[j]+(D_i-D_j-1)\times G_j+R_j-P_i\space|\space0\leq j<i\text{,}dp[j]\geq 0\}\space}$
化簡一下
$\color{white}{\space dp[i]=max\{G_j\times D_i + dp[j]-(D_j+1)\times G_j +R_j\space|\space0\leq j<i\text{,}dp[j]\geq 0\}-P_i\space}$
很經典的斜率優化形式
會特別強調$\color{white}{\space dp[j]\geq 0\space}$是因為機器買進後如果錢是負的，就表示其實當下你根本沒錢買這台機器
這裡我直接令$\color{white}{\space dp[0]=C\space}$，並在最後把第$\color{white}{\space D+1\space}$天當成一台買進買出生產都是0的機器，答案就是買進最後這台的DP值了

一般斜率優化通常都會利用「斜率的單調性」配合「參數的單調性」來優化至$\color{white}{\space O(N)\space}$
可是這題卻少了「斜率的單調性」，因為$\color{white}{\space G_j\space}$並不遞增

所以我們必須要維護「動態凸包」
理念大約是拿一個set，裡面放許多直線，在這題的話就是維護上凸包這樣
由於這題有「參數的單調性」，所以不用對線二分搜，從前面硬砍就好
最終問題就回到了實作動態凸包了

這裡我直接丟線進去
1.先把斜率相同的砍掉
2.再檢查自己會不會被兩側的直線完全覆蓋
3.往前砍
4.往後砍
大概是這樣的順序(?)，詳細可以看我的code(不過由於第一次實作動態凸包，醜醜的請見諒><)

最後總複雜度均攤$\color{white}{\space O(NlgN)\space}$~

順帶一提，這題在判斷直線交點的時候，因為求嚴謹使用整數的關係，所以要另外加個__int128來防止溢位@@~

	#pragma GCC optimize("Ofast")
	#include <bits/stdc++.h>
	#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	#define ll long long
	#define pb push_back
	#define F first
	#define S second
	#define MEM(i,j) memset(i,j,sizeof i)
	#define pii pair<ll,ll>
	#define pll pair<long long,long long>
	#define MP make_pair
	#define ET cout << "\n"
	#define DB(a,s,e) {for(ll i=s;i<e;i++) cout << a[i] << " ";ET;}
	using namespace std;
	struct mode
	{
	ll d,p,r,g;
	bool operator<(const mode &a)const{
	return d<a.d;
	}
	}mach[100001];
	struct lines
	{
	ll m,k;
	bool operator<(const lines&x)const{
	return m<x.m;
	}
	};
	set<lines> convex;
	const ll INF=5e18;
	ll value(lines a,ll x)
	{
	return a.m*x+a.k;
	}
	void insert(lines x)
	{
	auto p=convex.lower_bound(x),q=p,r=p;
	if(p!=convex.end())
	{
	if(p->m==x.m)
	if(p->k>=x.k) return;
	else convex.erase(p);
	}
	convex.insert(x);
	p=convex.find(x);
	if(p!=convex.begin())
	{
	q=p,q--,r=p,r++;
	if(r!=convex.end())
	{
	if((__int128)(q->k-r->k)*(p->m-q->m)<=(__int128)(q->k-p->k)*(r->m-q->m))
	return convex.erase(p),void();
	}
	}
	while(p!=convex.begin())
	{
	q=p,q--;
	if(q==convex.begin()) break;
	r=q,r--;
	if((__int128)(r->k-p->k)*(q->m-r->m)>(__int128)(r->k-q->k)*(p->m-r->m)) break;
	convex.erase(q);
	}
	while(p!=convex.end())
	{
	q=p,q++;
	if(q==convex.end()) break;
	r=q,r++;
	if(r==convex.end()) break;
	if((__int128)(p->k-r->k)*(q->m-p->m)>(__int128)(p->k-q->k)*(r->m-p->m)) break;
	convex.erase(q);
	}
	}
	bool fight(ll x)
	{
	auto p=convex.begin();
	++p;
	return value(*convex.begin(),x)<=value(*p,x);
	}
	int main()
	{jizz
	ll N,C,D,i,j,k,ans=0,dp;
	cin >> N >> C >> D;
	for(i=1;i<=N;++i)
	cin >> mach[i].d >> mach[i].p >> mach[i].r >> mach[i].g;
	sort(mach+1,mach+N+1);
	for(i=k=1,insert(lines{0,C});i<=N;i=k)
	{
	while(k<=N && mach[k].d==mach[i].d)
	{
	while(convex.size()>=2 && fight(mach[k].d)) convex.erase(convex.begin());
	dp=value(*convex.begin(),mach[k].d)-mach[k].p;
	if(dp>=0) insert(lines{mach[k].g,dp-(mach[k].d+1)*mach[k].g+mach[k].r});
	++k;
	}
	}
	while(convex.size()>=2 && fight(D+1)) convex.erase(convex.begin());
	cout << value(*convex.begin(),D+1) << "\n";
	}

view raw tioj1921.cpp hosted with ❤ by GitHub