這裡 是這題完整的想法以及支持在線的作法,特地再寫一篇是因為像操作分治一類轉離線後的作法不僅code量少,時間和空間上的表現也都很優秀。
平衡樹維護凸包我寫得要死要活寫了三天,操作分治40min就AC了,而且de最久的bug依然是__int128.....這數據實在是太坑了。
和整體二分的思想類似,只不過算法本身並沒有二分搜的性質,而是單純利用分治的特性讓複雜度從O(n^2)掉成O(nlogn)。
剩下的就參考code吧,概念和實作都算挺好懂的。
#define LL __int128 #include<bits/stdc++.h> using namespace std; const LL maxn=100000+5; struct Machine { LL day,price,resold,gene; bool operator < (const Machine& rhs) const {return day<rhs.day;} }Mac[maxn]; struct Line { LL slope,inter; Line(LL s,LL i):slope(s),inter(i) {} LL getVal(LL x){return slope*x+inter;} bool operator < (const Line& rhs) const {return slope<rhs.slope || (slope==rhs.slope && inter<rhs.inter);} }; LL N,C,D; vector<Line> line,hull; LL dp[maxn]; bool check(Line& L0,Line& L1,Line& L2) { return (L2.inter-L0.inter)*(L0.slope-L1.slope)< (L0.slope-L2.slope)*(L1.inter-L0.inter); } void update(LL tL,LL tR) { LL tM=tL+(tR-tL)/2; line.clear(); for(LL i=tL;i<=tM;i++) if(dp[i]>=Mac[i].price) line.push_back(Line(Mac[i].gene,Mac[i].resold-Mac[i].price+dp[i]-(Mac[i].day+1)*Mac[i].gene)); sort(line.begin(),line.end()); hull.clear(); for(Line now:line) { while(hull.size() && hull[hull.size()-1].slope==now.slope) hull.pop_back(); while(hull.size()>1 && check(hull[hull.size()-2],hull[hull.size()-1],now)) hull.pop_back(); hull.push_back(now); } LL now=0; for(LL i=tM+1;i<=tR;i++) { LL day=Mac[i].day; while(now+1<hull.size() && hull[now].getVal(day)<hull[now+1].getVal(day)) now++; dp[i]=max(dp[i],hull[now].getVal(day)); } } void CDQ(LL L,LL R) { if(L==R) return; LL M=L+(R-L)/2; CDQ(L,M); update(L,R); CDQ(M+1,R); } int main() { // freopen("in","r",stdin); long long kase=0,NN,CC,DD; while(scanf("%lld%lld%lld",&NN,&CC,&DD)==3 && NN && CC && DD) { N=NN,C=CC,D=DD; memset(dp,0,sizeof dp); for(long long i=1,a,b,c,d;i<=N;i++) {scanf("%lld%lld%lld%lld",&a,&b,&c,&d);Mac[i].day=a,Mac[i].price=b,Mac[i].resold=c,Mac[i].gene=d;} Mac[0]=Machine{0,0,C,0}; Mac[N+1]=(Machine){D+1,0,0,0}; sort(Mac,Mac+N+2); CDQ(0,N+1); printf("Case %lld: %lld\n",++kase,(long long)dp[N+1]); } }
沒有留言:
張貼留言