2019 - 截柱子
时间限制 : 1 秒
内存限制 : 128 MB
有n根柱子竖在地面上排成一排，每根柱子都可以从顶端截下一段以此来调整为任意高度，但是，柱子被截后剩下的高度必须是大于等于1的整数。相邻两根柱子的距离为w。现在要用一条绳子从第一根柱子的端点按顺序经过每一根柱子的端点到达最后一根绳子的端点，求这根绳子最长需要用多长？
题目输入
第一行输入一个数T，表示测试数据个数，对于每个测试数据，第一行输入两个整数n，w，分别表示柱子个数和相邻两根柱子的距离，第二行输入n个整数，分别表示每根柱子的初始高度
数据范围：
0<n<=100
0<w<=10
0<每根柱子的初始高度<=100
题目输出
对于每个测试数据，输出一个数，表示绳子最长需要多长，答案保留3位小数。
输入/输出样例
输入格式
2 3 2 3 3 3 4 10 1 1 1 1
输出格式
5.657 30.000
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; }