【POJ3612】【USACO 2007 Nov Gold】 1.Telephone Wire 动态调节

【POJ3612】【USACO 2007 Nov Gold】 1.Telephone Wire 动态调节

大家好,又见面了,我是全栈君,今天给大家准备了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账号...

(0)


相关推荐

  • Matlab读取txt数据的实用方法[通俗易懂]

    Matlab读取txt数据的实用方法[通俗易懂]需求有个朋友需要我帮忙写个matlab脚本读取100个txt文档的实验数据,这些文档的结构相同,分为四列,从第一列到第四列依次是时间、位置、速度、加速度。读取完数据之后需要对数据进行处理,具体的处理方式是:提取以0.002为采样周期的数据,分类存储起来。文件内容是这样的:技术难点技术难点在于,这些文件中的数据是从一个软件中仿真得到的,由于采用的是变步长仿真,因此采样时间不统一,很难采用对…

  • 基于OpenCv的人脸识别(Python完整代码)

    基于OpenCv的人脸识别(Python完整代码)目前人脸识别有很多较为成熟的方法,这里调用OpenCv库,而OpenCV又提供了三种人脸识别方法,分别是LBPH方法、EigenFishfaces方法、Fisherfaces方法。本文采用的是LBPH(LocalBinaryPatternsHistogram,局部二值模式直方图)方法。opencv是一个开源的的跨平台计算机视觉库,内部实现了图像处理和计算机视觉方面的很多通用算法,对于python而言,在引用opencv库的时候需要写为importcv2。其中,cv2是opencv的C++命名空间名称

  • java实现敏感词过滤「建议收藏」

    java实现敏感词过滤「建议收藏」项目中的需要,对用户的输入进行敏感词的过滤,使用的是DFT算法,敏感词可以从数据库进行读取和配置.把代码整理了一下,可以直接使用完整工程下载地址:https://download.csdn.net/download/a897180673/10278921一共三个类,1个测试类,1个从数据库加载敏感词类,一个是实现DFT算法的类,具体的算法可以去研究.首先是从数据库加…

  • jlink 与 swd 接口定义

    jlink 与 swd 接口定义1.JLink介绍J-Link是SEGGER公司为支持仿真ARM内核推出的JTAG仿真器。J-Link支持所有基于ARM架构的处理器或微控制器配合IAREWAR,ADS,KEIL等集成开发环境进行开发过程中进行单步控制执行调试。J-Link除了可以配合集成开发环境进行调试程序,进行程序下载之外,J-Link还可以单独使用。比如在产品的生产环节中,就可以单独使用J-Link进行固件的下载。JLink,SWD接口定义缺口向左,左边为JLink接口定义,右边为SWD接口定义JTAG

  • js的常见的三种密码加密方式-MD5加密、Base64加密和解密和sha1加密详解总结

    js的常见的三种密码加密方式-MD5加密、Base64加密和解密和sha1加密详解总结写在前面写前端的时候,很多的时候是避免不了注册这一关的,但是一般的注册是没有任何的难度的,无非就是一些简单的获取用户输入的数据,然后进行简单的校验以后调用接口,将数据发送到后端,完成一个简单的注册的流程,那么一般来说,密码是不做加密的。但是也有一些数据库里面存放的是加密后的密码,这样有一个比较安全的地方在于,即使黑客将用户输入的文本密码得到了,也不知道具体是什么,因为密码是经过加密的。今天就简单的…

  • Stopwatch用法

    Stopwatch用法获取系统时间计算System.currentTimeMillis()Stopwatch对程序部分代码进行计时(ms级别),适用于同步单线程代码块。StopWatch实例一次只能开启一个task,不能同时start多个task,并且在该task未stop之前不能start一个新的task,必须在该taskstop之后才能开启新的task,若要一次开启多个,需要new不同的StopWatch实例//只输出运行多少秒Stopwatchstopwatch=Stopwatch.creat.

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号