【UESTC 594】我要长高

题目连接：https://vjudge.net/problem/UESTC-594

韩父有NN个儿子，分别是韩一，韩二…韩NN。由于韩家演技功底深厚，加上他们间的密切配合，演出获得了巨大成功，票房甚至高达20002000万。舟子是名很有威望的公知，可是他表面上两袖清风实则内心阴暗，看到韩家红红火火，嫉妒心遂起，便发微薄调侃韩二们站成一列时身高参差不齐。由于舟子的影响力，随口一句便会造成韩家的巨大损失，具体亏损是这样计算的，韩一，韩二…韩NN站成一排，损失即为C×C×（韩ii与韩i+1i+1的高度差（1≤i<N1≤i<N））之和，搞不好连女儿都赔了.韩父苦苦思索，决定给韩子们内增高（注意韩子们变矮是不科学的只能增高或什么也不做），增高11cm是很容易的，可是增高1010cm花费就很大了，对任意韩ii，增高HHcm的花费是H2H2.请你帮助韩父让韩家损失最小。

Input

有若干组数据，一直处理到文件结束。

每组数据第一行为两个整数：韩子数量NN(1≤N≤500001≤N≤50000)和舟子系数CC(1≤C≤1001≤C≤100)

接下来NN行分别是韩i的高度(1≤hi≤1001≤hi≤100)。

Output

对每组测试数据用一行输出韩家的最小损失。

Sample Input

5 2 2 3 5 1 4

Sample Output

15

Hint

输入数据多请使用scanf代替cin

题解：我连线性Dp都没一次过吗（哭了），先讲下N*H*H的算法吧。（我一开始初始化有问题）

           第一层i先枚举n个人，第二次枚举n个人的身高j，第三层枚举k,即第i-1个人的身高。

#include<iostream> #include<algorithm> #include<queue> #include<cmath> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; const int oo=0x3f3f3f3f; const int N=50005; int fun,n,c,a[N],dp[N][101]; int ans=oo; int main(){freopen("1685.in","r",stdin);freopen("1685.out","w",stdout);scanf("%d %d",&n,&c);memset(dp,0x3f,sizeof(dp));scanf("%d",&a[1]);for(int j=a[1];j<=100;j++){dp[1][j]=(j-a[1])*(j-a[1]);//cout<<dp[1][j]<<endl; }for(int i=2;i<=n;i++)scanf("%d",&a[i]);for(int i=2;i<=n;i++){//dp[i][a[i]]=0;for(int j=a[i];j<=100;j++){for(int k=a[i-1];k<=100;k++){fun=dp[i-1][k]+abs(j-k)*c+(a[i]-j)*(a[i]-j);dp[i][j]=min(dp[i][j],fun);} }}for(int i=0;i<=100;i++)ans=min(dp[n][i],ans);printf("%d\n",ans);return 0; }

 

转载于:https://www.cnblogs.com/wuhu-JJJ/p/11335014.html

总结

以上是生活随笔为你收集整理的【UESTC 594】我要长高的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。