大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
意甲冠军:
一些树高给出。行一种操作:把某棵树增高h,花费为h*h。
操作完毕后连线,两棵树间花费为高度差*定值c。
求两种花费加和最小值。
题解:
跟NOIP2014 D1T3非常像。
暴力动规是O(1*10^9)会T
所以单调队列一下,每颗树扫两遍结束。
完事,看水代码吧。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 101000 #define M 105 #define inf 0x3f3f3f3f using namespace std; int f[2][M],g[2][M],n,c; int now,last; int h[N]; int main() { // freopen("test.in","r",stdin); int i,j,k; scanf("%d%d",&n,&c); for(i=1;i<=n;i++)scanf("%d",&h[i]); now=0,last=1; for(i=1;i<=n;i++) { now^=1,last^=1; int temp=inf; for(j=100;j>=h[i];j--) { temp=min(temp+c,f[last][j]); f[now][j]=temp+(j-h[i])*(j-h[i]); } temp=inf; for(j=1;j<=100;j++) { temp=min(temp+c,f[last][j]); f[now][j]=min(f[now][j],temp+(j-h[i])*(j-h[i])); if(j<h[i])f[now][j]=inf; } } int ans=inf; for(i=1;i<=100;i++)ans=min(ans,f[now][i]); printf("%d\n",ans); return 0; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117188.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...