企业官网建设流程全解析

关于旅游类网站建设设计方案,wordpress内容插件,开一个做网站的工作室,品牌网站建设 d磐石网络P4072 [SDOI2016] 征途 题目描述 Pine 开始了从 SSS 地到 TTT 地的征途。 从 SSS 地到 TTT 地的路可以划分成 nnn 段#xff0c;相邻两段路的分界点设有休息站。 Pine 计划用 mmm 天到达 TTT 地。除第 mmm 天外#xff0c;每一天晚上 Pine 都必须在休息站过夜。所以…P4072 [SDOI2016] 征途题目描述Pine 开始了从S SS地到T TT地的征途。从S SS地到T TT地的路可以划分成n nn段相邻两段路的分界点设有休息站。Pine 计划用m mm天到达T TT地。除第m mm天外每一天晚上 Pine 都必须在休息站过夜。所以一段路必须在同一天中走完。Pine 希望每一天走的路长度尽可能相近所以他希望每一天走的路的长度的方差尽可能小。帮助 Pine 求出最小方差是多少。设方差是v vv可以证明v × m 2 v\times m^2v×m2是一个整数。为了避免精度误差输出结果时输出v × m 2 v\times m^2v×m2。输入格式第一行两个数n , m n, mn,m。第二行n nn个数表示n nn段路的长度。输出格式一个数最小方差乘以m 2 m^2m2后的值。输入输出样例 #1输入 #15 2 1 2 5 8 6输出 #136说明/提示数据范围及约定对于30 % 30\%30%的数据1 ≤ n ≤ 10 1 \le n \le 101≤n≤10对于60 % 60\%60%的数据1 ≤ n ≤ 100 1 \le n \le 1001≤n≤100对于100 % 100\%100%的数据1 ≤ n ≤ 3000 1 \le n \le 30001≤n≤3000。保证从S SS到T TT的总路程不超过3 × 1 0 4 3\times 10^43×104。2 ≤ m ≤ n 2 \leq m \leq n2≤m≤n每段路的长度为不超过3 × 1 0 4 3 \times 10^43×104的正整数。思路单调队列斜率优化代码见下#includebits/stdc.husingnamespacestd;longlongn,m,a[3005],b[3005],f[3005][3005],op0;intmain(){cinnm;for(inti1;in;i){cina[i];b[i]b[i-1]a[i];}memset(f,62,sizeof(f));for(inti1;in;i){f[i][1]b[i]*b[i];for(intj2;jmin((longlong)i,m);j){f[i][j]1e187;for(intkmax(0,i-100);ki-1;k){f[i][j]min(f[i][j],f[k][j-1](b[i]-b[k])*(b[i]-b[k]));}//couti j f[i][j]endl;}}coutf[n][m]*m-b[n]*b[n]endl;return0;}