二分法只適用與線性函數(shù)，當函數(shù)脫離線性而呈現(xiàn)凸性或者凹性的時候，三分是很有必要的。

三分過程如下圖：

凸函數(shù)：

凹函數(shù)：

實現(xiàn)方法：

double Calc(double p) {/*...*/ }double Solve(double MIN, double MAX) {double Left, Right;double mid, midmid;double mid_area = 0, midmid_area = 0; //***Left = MIN; Right = MAX;while (Left + eps < Right) {mid = (Left + Right) / 2;midmid = (mid + Right) / 2;mid_area = Calc(mid);midmid_area = Calc(midmid);if (midmid_area - mid_area > eps) Right = midmid;else Left = mid;}return mid_area; }

?

?

??

?例題：HDU?4355 ( Party All the Time )?

?

View Code #include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <cstring> #include <algorithm> #include <string> #include <set> #include <ctime> #include <queue> #include <map> #include <sstream>#define CL(arr, val) memset(arr, (val), sizeof(arr)) #define REP(i, n) for((i) = 0; (i) < (n); ++(i)) #define FOR(i, l, h) for((i) = (l); (i) <= (h); ++(i)) #define FORD(i, h, l) for((i) = (h); (i) >= (l); --(i)) #define L(x) (x) << 1 #define R(x) (x) << 1 | 1 #define MID(l, r) ((l) + (r)) >> 1 #define Min(x, y) (x) < (y) ? (x) : (y) #define Max(x, y) (x) < (y) ? (y) : (x) #define E(x) (1 << (x)) #define iabs(x) ((x) > 0 ? (x) : -(x))typedef long long LL; const double eps = 1e-6; const double inf = 1000000000;using namespace std;const int N = 50010;struct node {double p;double w; } q[N];int n;double Calc(double p) {double tmp = 0, d;for(int i = 0; i < n; ++i) {d = abs(q[i].p - p);tmp += d*d*d*q[i].w;}return tmp; }double Solve(double MIN, double MAX) {double Left, Right;double mid, midmid;double mid_area = 0, midmid_area = 0;Left = MIN; Right = MAX;while (Left + eps < Right) {mid = (Left + Right) / 2;midmid = (mid + Right) / 2;mid_area = Calc(mid);midmid_area = Calc(midmid);if (midmid_area - mid_area > eps) Right = midmid;else Left = mid;}//printf("%.10f\n", mid_area);return mid_area; }int main() {//freopen("data.in", "r", stdin);int t, j, cas = 0;double mx, mi;scanf("%d", &t);while(t--) {scanf("%d", &n);mx = -inf, mi = inf;for(j = 0; j < n; ++j) {scanf("%lf%lf", &q[j].p, &q[j].w);if(mx < q[j].p) mx = q[j].p;if(mi > q[j].p) mi = q[j].p;}double ans = Solve(mi, mx) + 0.5;printf("Case #%d: %d\n", ++cas, int(ans));}return 0; }

?

?POJ 3301

方法，對坐標系進行(0, 180]度的旋轉(zhuǎn)，然后每個點得到新的坐標，找到最上面，最下面，最左面和最右面的點，然后就行確定當前旋轉(zhuǎn)角度的面積。

x' = x*cos(th) + y*sin(th);

y' = y*cos(th) - x*sin(th);

View Code //#pragma comment(linker,"/STACK:327680000,327680000") #include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <cstring> #include <algorithm> #include <string> #include <set> #include <functional> #include <numeric> #include <sstream> #include <stack> #include <map> #include <queue>#define CL(arr, val) memset(arr, val, sizeof(arr)) #define REP(i, n) for((i) = 0; (i) < (n); ++(i)) #define FOR(i, l, h) for((i) = (l); (i) <= (h); ++(i)) #define FORD(i, h, l) for((i) = (h); (i) >= (l); --(i)) #define L(x) (x) << 1 #define R(x) (x) << 1 | 1 #define MID(l, r) (l + r) >> 1 #define Min(x, y) (x) < (y) ? (x) : (y) #define Max(x, y) (x) < (y) ? (y) : (x) #define E(x) (1 << (x)) #define iabs(x) (x) < 0 ? -(x) : (x) #define OUT(x) printf("%I64d\n", x) #define Read() freopen("data.in", "r", stdin) #define Write() freopen("data.out", "w", stdout);typedef long long LL; const double eps = 1e-8; const double pi = acos(-1.0); const double inf = ~0u>>2;using namespace std;const int N = 50;struct node {double x, y; }p[N];int n;double Calc(double th) {double l = inf, r = -inf, d = inf, u = -inf;double xx, yy, t;for(int i = 0; i < n; ++i) {t = th*pi/180.0;xx = p[i].x*cos(t) + p[i].y*sin(t);yy = p[i].y*cos(t) - p[i].x*sin(t);l = min(l, xx); d = min(d, yy);r = max(r, xx); u = max(u, yy);}return max((r - l)*(r - l), (u - d)*(u - d)); }double Solve(double MIN, double MAX) {double Left, Right;double mid, midmid;double mid_area = 0, midmid_area = 0;Left = MIN, Right = MAX;while(Left + eps < Right) {mid = (Left + Right) / 2.0;midmid = (mid + Right) / 2.0;mid_area = Calc(mid);midmid_area = Calc(midmid);if(midmid_area - mid_area > eps) Right = midmid;else Left = mid;}return mid_area; }int main() {//Read();int T, i;scanf("%d", &T);while(T--) {scanf("%d", &n);for(i = 0; i < n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y);printf("%.2f\n", Solve(0, 180));}return 0; }

?

?

??

??

?

轉(zhuǎn)載于:https://www.cnblogs.com/vongang/archive/2012/10/30/2745988.html

總結(jié)

以上是生活随笔為你收集整理的三分法解决凸（凹）函数极值问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。