2019 - 截柱子
有n根柱子竖在地面上排成一排，每根柱子都可以从顶端截下一段以此来调整为任意高度，但是，柱子被截后剩下的高度必须是大于等于1的整数。相邻两根柱子的距离为w。现在要用一条绳子从第一根柱子的端点按顺序经过每一根柱子的端点到达最后一根绳子的端点，求这根绳子最长需要用多长？
Input
第一行输入一个数T，表示测试数据个数，对于每个测试数据，第一行输入两个整数n，w，分别表示柱子个数和相邻两根柱子的距离，第二行输入n个整数，分别表示每根柱子的初始高度
数据范围：
0<n<=100
0<w<=10
0<每根柱子的初始高度<=100
Output
对于每个测试数据，输出一个数，表示绳子最长需要多长，答案保留3位小数。
Examples
Input
2 3 2 3 3 3 4 10 1 1 1 1
Output
5.657 30.000
Hint
样例1可以将柱子调整为3 1 3，第一根柱子到第二根柱子需要绳子长度和第二根柱子到第三根柱子需要绳子长度均为根号8，因此相加为2根号8，约为5.657.
Solution C++
#include <stdio.h> #include <string.h> #include <iostream> #include <string> #include <queue> #include <stack> #include <math.h> #include <map> #include <vector> #include <list> #include <stdlib.h> #include <set> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,s,t) for(int i=s;i<t;i++) #define red(i,s,t) for(int i=s-1;i>=t;i--) #define ree(i,now) for(int i=head[now];i!=-1;i=edge[i].next) #define clr(a,v) memset(a,v,sizeof a) #define MID(x,y) int mid=(x+y)>>1 #define L t<<1 #define R t<<1|1 #define mk(i,j) make_pair(i,j) #define SQR(x) ((x)*(x)) inline int input(){ int ret=0;int isN=0;char c=getchar(); while(c<'0' || c>'9'){ if(c=='-') isN=1; c=getchar(); } while(c>='0' && c<='9'){ ret=ret*10+c-'0'; c=getchar(); } return isN?-ret:ret; } inline void output(int x){ if(x<0){ putchar('-');x=-x; } int len=0,data[11]; while(x){ data[len++]=x%10;x/=10; } if(!len) data[len++]=0; while(len--) putchar(data[len]+48); putchar('\n'); } inline double dis(int a,int b,int w){ return sqrt(SQR(a-b)+SQR(w)); } double dp[110][110]; int n,w,a[110]; int main(){ int t=input(); while(t--){ n=input(),w=input(); rep(i,0,101) rep(j,0,101) dp[i][j]=0.0; rep(i,1,n+1) a[i]=input(); rep(i,1,a[1]+1) dp[1][i]=0.0; rep(i,2,n+1){ rep(j,1,a[i]+1){ rep(k,1,a[i-1]+1){ dp[i][j]=max(dp[i][j],dp[i-1][k]+dis(j,k,w)); } } } double ans=0; rep(i,1,a[n]+1) ans=max(ans,dp[n][i]); printf("%.3lf\n",ans); } return 0; }
Hint
样例1可以将柱子调整为3 1 3，第一根柱子到第二根柱子需要绳子长度和第二根柱子到第三根柱子需要绳子长度均为根号8，因此相加为2根号8，约为5.657.