电子商务网站建设流程图,专业从事网站开发公司,网站推广的具体方案,农村自建房设计题目描述 最近#xff0c;Farmer John的奶牛们越来越不满于牛棚里一塌糊涂的电话服务 于是#xff0c;她们要求FJ把那些老旧的电话线换成性能更好的新电话线。 新的电话线架设在已有的N(2 N 100,000)根电话线杆上#xff0c; 第i根电话线杆的高度为height_i米(1 Farmer John的奶牛们越来越不满于牛棚里一塌糊涂的电话服务 于是她们要求FJ把那些老旧的电话线换成性能更好的新电话线。 新的电话线架设在已有的N(2 N 100,000)根电话线杆上 第i根电话线杆的高度为height_i米(1 height_i 100)。 电话线总是从一根电话线杆的顶端被引到相邻的那根的顶端 如果这两根电话线杆的高度不同那么FJ就必须为此支付 C*电话线杆高度差(1 C 100)的费用。当然你不能移动电话线杆 只能按原有的顺序在相邻杆间架设电话线。Farmer John认为 加高某些电话线杆能减少架设电话线的总花费尽管这项工作也需要支出一定的费用。 更准确地如果他把一根电话线杆加高X米的话他得为此付出X^2的费用。 请你帮Farmer John计算一下如果合理地进行这两种工作他最少要在这个电话线改造工程上花多少钱。 输入 第1行: 2个用空格隔开的整数N和C 第2..N1行: 第i1行仅有一个整数height_i 输出 第1行: 输出Farmer John完成电话线改造工程所需要的最小花费 样例输入 5 2 2 3 5 1 4 样例输出 15 题解 dp优化 每个电线杆加高之后的最高高度肯定不超过高度最大值maxh这是显然的。 首先有最基本的思路 f[i][j]表示第i个柱子高度为j时的最小花费。 那么就有f[i][j](j-h[i])2min(f[i-1][k]c*abs(k-j)),kmaxh 这样时间复杂度是O(nh2)会超时肯定要优化。 怎么优化呢可以把绝对值拆开于是状态转移方程变为 f[i][j](j-h[i])2min(f[i-1][k]-c*k)c*j,kj (j-h[i])2min(f[i-1][k]c*k)-c*j,kj 那么我们只要分别维护f[i-1][k]-c*k,kj和f[i-1][k]c*k,kj的最小值即可可以递推求出。 设min1[i][j]为kj时f[i][k]-c*k的最小值min2[i][j]为kj时f[i][k]c*k的最小值。 那么就有min1[i][j]min(min1[i][j-1],f[i][j]-c*j) min2[i][j]min(min2[i][j1],f[i][j]c*j) 以及f[i][j](j-h[i])2min(min1[i-1][j]c*j,min2[i-1][j]-c*j)。 注意公式中有的是i有的是i-1不要弄混。 于是时间复杂度被优化到了O(nh)解决了时间问题。 然而题目空间要求是64MB这样开二维数组会MLE。 所以我使用了滚动数组黑科技应该不难理解注意细节。 听说少开一个二维数组好像也能过没试过反正滚动数组应该是最好的做法了吧。 还有柱子高度不能降低所以注意一下循环起始点和终止点。 #include cstdio
#include cstring
#include algorithm
using namespace std;
int f[102] , h[100002] , min1[102] , min2[102];
int main()
{int n , c , m 0 , i , j , ans 0x3f3f3f3f;scanf(%d%d , n , c);for(i 1 ; i n ; i )scanf(%d , h[i]) , m max(m , h[i]);memset(f , 0x3f , sizeof(f));for(i h[1] ; i m ; i )f[i] (i - h[1]) * (i - h[1]);for(i 2 ; i n ; i ){memset(min1 , 0x3f , sizeof(min1));memset(min2 , 0x3f , sizeof(min2));for(j h[i - 1] ; j m ; j )min1[j] min(min1[j - 1] , f[j] - c * j);for(j m ; j 1 ; j -- )min2[j] min(min2[j 1] , j h[i - 1] ? f[j] c * j : 0x3f3f3f3f);for(j h[i] ; j m ; j )f[j] (j - h[i]) * (j - h[i]) min(min1[j] c * j , min2[j] - c * j);}for(i h[n] ; i m ; i )ans min(ans , f[i]);printf(%d\n , ans);return 0;
} 转载于:https://www.cnblogs.com/GXZlegend/p/6306232.html
