KIDx 的解题报告
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2241
解题思路:
由题意得:【设题目所给m个点存放到点结构p[m]中】
F = n/(x^2)
设Y是第i-1个点跟第i个点连线的方程【设k是这2点连线的斜率】
则:【根据题目:i<j Xi<Xj 且 Yi<=Yj】
Y = k * (x-p[i-1].x) + p[i-1].y
设总的函数 = Z
则Z = Y + F = n/(x^2) + k * (x-p[i-1].x) + p[i-1].y
即:Z = n/(x^2) + k*x + (p[i-1].y - k*p[i-1].x)
由于点已经给出,所以绿色部分为常数部分,不会影响函数单调性
∴可以提出来,不用放到代码中Z函数内,因为三分里要运行很多次Z函数,这样无意中就增加了运行时间
如图:
简单联想可知对于第k段来说,Z函数有可能是单调的,也有可能是先减后增的函数,但是对于(0,+无穷)来说,Z函数可能有多个极值,所以必须分段【可以从分段函数的角度理解】进行三分求最小值
#include <iostream>
using namespace std;
#define eps 1e-4
#define M 10005
const double inf = 1e100; //定义无穷大
int n, m;
struct point{
int x, y;
}p[M];
double Z (double x, double k) {return n/(x*x) + k*x;}
int main()
{
int i;
double l, r, mid1, mid2, mins, tp1, tp2;
while (~scanf ("%d%d", &m, &n))
{
for (i = 0; i < m; i++)
scanf ("%d%d", &p[i].x, &p[i].y);
mins = inf;
for (i = 1; i < m; i++) //分段求解
{
l = p[i-1].x, r = p[i].x;
double k = (p[i].y - p[i-1].y + 0.0) / (p[i].x - p[i-1].x);//求斜率
while (r - l > eps) //三分逼近函数极值
{
mid1 = l + (r-l)/3;
mid2 = r - (r-l)/3;
tp1 = Z (mid1, k);
tp2 = Z (mid2, k);
if (tp1 > tp2)
l = mid1;
else r = mid2;
}
tp1 += p[i-1].y - k*p[i-1].x; //把常数加上
if (mins > tp1) mins = tp1; //更新最小值
}
printf ("%.3f\n", mins);
}
return 0;
}
- 大小: 8.1 KB
- 大小: 166.7 KB
分享到:
相关推荐
算法设计与分析实验六:使用动态规划算法解决存钱问题(java实现、hdu1114)(csdn)————程序
hdu ACM 高级程序设计习题集——全文 里面有程序的详细解释
本压缩包内包含杭电ACM集训的课件PPT,较为详细的介绍了动态规划,计算几何,贪心算法, 搜索,二分图及其应用,母函数及其应用,组合博弈入门,并查集,递推求解等常用算法
HDU图论题目分类
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu题目分类
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
杭州电子科技大学计算机考研信息汇总 作者: GitHub:ztygalaxy GitHub Pages: 适用报考范围: 杭电计算机学院计算机相关专业,不定期更新 本系列只在GitHub不定期更新,其他平台非本人维护或停止维护,转载请标明...
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
其中有pku、hdu、zoj等各大oj的题目分类,pku的oj比较详细一点,按不同算法进行分类,均系从网上自行搜集的。
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。