首页 > 代码库 > hdu1330（递推）
hdu1330（递推）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1330
分析：经典问题，n 块相同的木板重叠，最多能够伸出桌面多远
对于n张卡片的最佳摆法，我们只需要在n-1张卡片的摆法下面加一张边缘与桌檐重合的卡片，并将所有卡片一起向桌檐外移动。对于一种最佳摆法，其中心一定在桌檐上，所以一定符合杠杆原理，支点是桌檐。那么对于n张卡片的情况，我们假设第n张向外移动了x，那么前n-1张的重心就在桌檐外x，因为他们的重心在n-1张卡片时原本在桌檐上。第n张卡片的重心在桌檐内0.5-x处，那么我们可以列出杠杆平衡方程：(0.5-x)*1=x*(n-1)
解得：x=1/(2n)。可以推出，如果每块木板都是单位长，那么 n 块木板可以伸出桌面 (1 + 1/2 +
1/3 + … + 1/n) / 2 个单位的长度。
参考：http://gd2011.teacher.com.cn/UserLog/UserLogComment.aspx?UserlogID=15319
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define inf 1<<30#define mod 1000000007#define N 100010using namespace std;int main(){ int n; double a[100010]; a[1] = 0.5; for(int i = 2; i <= 100000; i++) a[i] = a[i-1] + 1.0/i/2; printf("# Cards Overhang\n"); while(scanf("%d",&n)>0) { printf("%5d%10.3lf\n",n,a[n]); }}
hdu1330（递推）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。