【題目描述】

對于給定的一個長度為N的正整數數列A[i]，現要將其分成M（M≤N）段，并要求每段連續，且每段和的最大值最小。

關于最大值最小：

例如一數列4 2 4 5 1要分成3段

將其如下分段：

[4 2][4 5][1]

第一段和為6，第2段和為9，第3段和為1，和最大值為9。

將其如下分段：

[4][2 4][5 1]

第一段和為4，第2段和為6，第3段和為6，和最大值為6。

并且無論如何分段，最大值不會小于6。

所以可以得到要將數列4 2 4 5 1要分成3段，每段和的最大值最小為6。

【輸入】

第1行包含兩個正整數N，M，第2行包含N個空格隔開的非負整數A[i]，含義如題目所述。

【輸出】

僅包含一個正整數，即每段和最大值最小為多少。

【輸入樣例】

5 3
4 2 4 5 1

【輸出樣例】

6

【源程序】

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> const double EPS = 1E-10; const int MOD = 1E9+7; const int N = 10000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std; struct Node{double x,y;Node(){}Node(double x,double y):x(x),y(y){} }a,b,c,d; double p,q,r; double getDis(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } double judge(Node e){Node left(c.x,c.y),right(d.x,d.y);int times=100;//控制三分次數while(times--){Node lmid,rmid;lmid.x=left.x+(right.x-left.x)/3;lmid.y=left.y+(right.y-left.y)/3;rmid.x=right.x-(right.x-left.x)/3;rmid.y=right.y-(right.y-left.y)/3;double dis1=getDis(lmid.x,lmid.y,d.x,d.y)/q+getDis(lmid.x,lmid.y,e.x,e.y)/r;double dis2=getDis(rmid.x,rmid.y,d.x,d.y)/q+getDis(rmid.x,rmid.y,e.x,e.y)/r;if(dis1<dis2){right.x=rmid.x;right.y=rmid.y;}else{left.x=lmid.x;left.y=lmid.y;}}return getDis(left.x,left.y,d.x,d.y)/q+getDis(left.x,left.y,e.x,e.y)/r+getDis(e.x,e.y,a.x,a.y)/p;} int main(){scanf("%lf%lf",&a.x,&a.y);scanf("%lf%lf",&b.x,&b.y);scanf("%lf%lf",&c.x,&c.y);scanf("%lf%lf",&d.x,&d.y);scanf("%lf%lf%lf",&p,&q,&r);Node left(a.x,a.y),right(b.x,b.y);int times=100;//控制三分次數while(times--){Node lmid,rmid;lmid.x=left.x+(right.x-left.x)/3;lmid.y=left.y+(right.y-left.y)/3;rmid.x=right.x-(right.x-left.x)/3;rmid.y=right.y-(right.y-left.y)/3;if(judge(lmid)<judge(rmid)){right.x=rmid.x;right.y=rmid.y;}else{left.x=lmid.x;left.y=lmid.y;}}printf("%.2lf",judge(left));return 0; }

?

總結

以上是生活随笔為你收集整理的传送带（信息学奥赛一本通-T1439）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。