POJ 1759 Garland

高度之间的关系可以改写成一个递推式：H_i+1 = 2H_i - H_i-1 + 2。Hn和Hi之间是正相关的。

思路见注释。（一开始是那么想的，其实不用矩阵快速幂，二分H₂也可以。

/*********************************************************
*            ------------------                          *
*   author AbyssalFish                                   *
**********************************************************/
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
#include<set>
#include
#include
#include
using namespace std;/*
Hi = (Hi-1+Hi+1) /2 - 1
Hi+1 = 2Hi - Hi-1 + 2
构造 matrix
Hi+1 |2 -1 2 | Hi
Hi  =|1  0 0 | Hi-1
1    |0  0 0 | 1
Hn一定是H1和H2的线性组合
矩阵快速幂以后，根据Hn求出H2
然后就可递推了*/#define check_mat(M)\
for(auto r: M){\for(auto e: r) cout<' ';\cout<<endl;\}typedef vector<int> row;
typedef vector mat;
const int n = 3;
mat operator *(mat&A, mat &B)
{mat R(n,row(n));for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){for(int k = 0; k < n; k++){R[i][j] += A[i][k]*B[k][j];}}}return R;
}mat operator ^(mat A, int q)
{mat R(n,row(n));for(int i = 0; i < n; i++) R[i][i] = 1;while(q){if(q&1) {R = R*A;}A = A*A;q >>= 1;}return R;
}const int MAX_N = 1e3;
int N;
double A;
double H[MAX_N];
mat M(n,row(n));#define check_var(v) cout<bool P(double Hn)
{H[1] = (Hn - M[0][1]*H[0] - M[0][2])/M[0][0];if(H[1] < 0.) return false;for(int i = 2; i < N-1; i++){H[i] = 2*H[i-1] - H[i-2] + 2;if(H[i] < 0.) {//check_var(H[i])return false;}}return true;
}//#define LOCAL
int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);
#endifM[0][0] = 2; M[0][1] = -1; M[0][2] = 2;M[1][0] = 1; M[2][2] = 1;scanf("%d%lf", &N, H);M = M^(N-2);//check_mat(M)double lb = 0, ub = 1e9, md;for(int i = 100; i--;){md = (lb+ub)/2;P(md) ? ub = md: lb = md;}printf("%.2f",(lb+ub)/2);return 0;
}

转载于:https://www.cnblogs.com/jerryRey/p/4972665.html

本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 162202241@qq.com 举报，一经查实，本站将立刻删除。

1313e

POJ 1759 Garland

取消回复欢迎您发表评论:

默认分类  深入嵌入式系统的 BootLoader

默认分类  kafka流处理平台

默认分类  大数据生态地图2.0：大数据的38种商业模式

默认分类  8.5 趣味游戏(1)

默认分类  制作JDK镜像

1313e

POJ 1759 Garland

取消回复欢迎您发表评论:

默认分类 深入嵌入式系统的 BootLoader

默认分类 kafka流处理平台

默认分类 大数据生态地图2.0：大数据的38种商业模式

默认分类 8.5 趣味游戏(1)

默认分类 制作JDK镜像

默认分类深入嵌入式系统的 BootLoader

默认分类大数据生态地图2.0：大数据的38种商业模式

默认分类制作JDK镜像