woc, 13年前的ZJOI就這么毒瘤的嘛。。。

題目鏈接: (bzoj)https://www.lydsy.com/JudgeOnline/problem.php?id=1859

(luogu)https://www.luogu.org/problemnew/show/P2589

題解: 大分類討論，預處理\(ints[i][j]\)表示碗\(i\)疊在\(j\)上，\(i\)的底部比\(j\)的底部要高多少

然后分類討論求此數組:

(1) \(i\)的下半徑比\(j\)的上半徑大，則等于\(j\)的高度

(2) \(i\)的上半徑比\(j\)的下半徑小，則等于零

(3) \(i\)的碗壁斜率大于\(j\)的碗壁斜率

(3.1) 若\(i\)的下半徑小于等于\(j\)的下半徑，則為零

(3.2) 若\(i\)的下半徑大于\(j\)的下半徑，則接觸點橫坐標為\(i\)的下半徑，通過\(j\)的一次函數計算高度即可

(4) \(i\)的碗壁斜率小于\(j\)的碗壁斜率

(4.1) 若\(i\)的上半徑大于等于\(j\)的上半徑，則接觸點為\(j\)的口處，通過\(i\)的一次函數計算高度

(4.2) 若\(i\)的上半徑小于\(j\)的上半徑，則(不妨先不考慮碗底)接觸點橫坐標為\(i\)的上半徑，通過\(j\)的一次函數計算高度

情況(4)最后求出來的高度和\(0\)取Max.

(5) 若\(i\)和\(j\)碗壁斜率相等

(5.1) 若\(i\)的下半徑小于等于\(j\)的下半徑，則高度為\(0\).

(5.2) 若\(i\)的下半徑大于\(j\)的上半徑，則接觸點橫坐標為\(i\)的下半徑，通過一次函數計算高度即可。

然后一個顯然的性質是一個碗疊在一摞碗上，它的疊放高度為和每個碗分別疊放的高度的Max.

這題……我還能說什么呢23333

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<algorithm> using namespace std;const int N = 9; struct Element {int h,r1,r2;double calc(double x) {return h*(x-(double)r1)/((double)r2-r1);} } a[N+3]; double hh[N+3]; int permu[N+3]; double ints[N+3][N+3]; int n;double intersect(int x,int y) { // printf("Intersect (%d,%d)\n",x,y);double ret;if(a[x].r1>a[y].r2) {ret = a[y].h;/* printf("Case 1\n");*/}else if(a[x].r2<a[y].r1) {ret = 0;/* printf("Case 2\n");*/}else if((a[y].r2-a[y].r1)*a[x].h>(a[x].r2-a[x].r1)*a[y].h){if(a[x].r1<=a[y].r1) {ret = 0;/* printf("Case 3.1\n");*/}else {ret = a[y].calc((double)a[x].r1);/* printf("Case 3.2\n");*/}}else if((a[y].r2-a[y].r1)*a[x].h<(a[x].r2-a[x].r1)*a[y].h){if(a[x].r2>=a[y].r2) {ret = a[y].h-a[x].calc(a[y].r2);/* printf("Case 4.1\n");*/} // else if(a[x].h*(a[y].r2-a[y].r1)<=a[y].h*(a[x].r2-a[y].r1)) {ret = 0;}else {ret = a[y].calc(a[x].r2)-a[x].calc(a[x].r2);/* printf("Case 4.2\n");*/}if(ret<0) ret = 0;}else{if(a[x].r1<=a[y].r1) {ret = 0;/* printf("Case 5.1\n");*/}else {ret = a[y].calc(a[x].r1);/* printf("Case 5.2\n");*/}} // printf("ret=%lf\n",ret);return ret; }double calc() { // printf("calc: "); for(int i=1; i<=n; i++) printf("%d ",permu[i]); puts("");double ret = 0.0;for(int i=1; i<=n; i++){hh[i] = 0;for(int j=1; j<i; j++){hh[i] = max(hh[i],hh[j]+ints[permu[i]][permu[j]]);}ret = max(ret,hh[i]+a[permu[i]].h);} // printf("Total=%lf\n",ret); puts("");return ret; }int main() {scanf("%d",&n);for(int i=1; i<=n; i++) scanf("%d%d%d",&a[i].h,&a[i].r1,&a[i].r2);for(int i=1; i<=n; i++) permu[i] = i;for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){if(i==j) continue;ints[i][j] = intersect(i,j);}}double ans = 1e6;do{ans = min(ans,calc());} while(next_permutation(permu+1,permu+n+1));printf("%d\n",(int)(ans+0.5));return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 1859 Luogu P2589 [ZJOI2006]碗的叠放 (计算几何)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。