TOP

HDU3714 Error Curves (单峰函数)
2014-11-23 21:58:39 】 浏览:10151
Tags:HDU3714 Error Curves 单峰 函数

大意:
给你n个二次函数Si(x),F(x) = max{Si(x)}
求F(x)在[0,1000]上的最小值。
S(x)=ax^2+bx+c
(0<=a<=100, |b|,|c|<=5000)
简单分析一下可知函数F(x)的图形是下凸函数,可以采用三分法求最值。
CODE:
#include
#include
using namespace std;
const int maxn = 10000 + 10;
int n, a[maxn], b[maxn], c[maxn];
double F(double x)
{
double ans = a[0]*x*x + b[0]*x + c[0];
for(int i=1; i
ans = max(ans, a[i]*x*x + b[i]*x +c[i]);
return ans;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i=0; i < n; ++i) scanf("%d%d%d", &a[i], &b[i], &c[i]);
double L = 0.0, R = 1000.0;
for(int i = 0; i < 100; ++i)
{
double m1 = L + (R - L)/3;
double m2 = R - (R - L)/3;
if(F(m1) < F(m2) ) R = m2;
else L = m1;
}
printf("%.4lf\n", F(L));
}
return 0;
}
求单峰函数的极值也可以用黄金分割法

HDU3714 Error Curves (单峰函数) https://www.cppentry.com/bencandy.php?fid=49&id=21358

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇poj 1631 Bridging signals (LIS .. 下一篇hdu4055 Number String