【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)


相关推荐

  • hash校验软件_hash加密

    hash校验软件_hash加密【Hash篇】HashTab一款可扩展资源管理器的哈希校验软件​ HashTab是一款非常优秀的Windows资源管理器扩展程序,它在资源管理器的属性窗口中添加了”文件校验”的标签,可以非常方便地校验文件的CRC32、MD5、SHA1等校验值,另外还可以迅速与其他文件进行哈希值比对!—【suy】文章目录【Hash篇】HashTab一款可扩展资源管理器的哈希校验软件1、自定义哈希算法2、文件比较功能3、下载地址总结1、自定义哈希算法​ HashTab可计算和显示来自二十多种流行的哈希算法的哈希值,

  • Android应用程序绑定服务(bindService)的过程源代码分析

    Android应用程序绑定服务(bindService)的过程源代码分析Android应用程序组件Service与Activity一样,既可以在新的进程中启动,也可以在应用程序进程内部启动;前面我们已经分析了在新的进程中启动Service的过程,本文将要介绍在应用程序内部绑定Service的过程,这是一种在应用程序进程内部启动Service的方法。     在前面一篇文章Android进程间通信(IPC)机制Binder简要介绍和学习计划中,我们就曾经提到,在A

  • Java 编码转换_java 判断文件编码

    Java 编码转换_java 判断文件编码中文各种编码间互相转换,非常有用哦,借鉴了公司的资料,转载本人不负任何责任,呵呵主要是用hcutf8.txt里面的内容根据转码替换,呵呵packageencoding;importjava.io.BufferedReader;importjava.io.InputStream;importjava.io.InputStreamReader;importjava.io.Unsupporte

  • ssm框架过时了吗_mybatis分页插件

    ssm框架过时了吗_mybatis分页插件日志如果一个数据库操作,出现了异常,我们需要排错,日志就是最好的助手曾经:sout,debug现在:日志工厂掌握STDOUT_LOGGINGLOG4Jlog4j什么是Log4j?我们可以控制日志信息输送的目的地是控制台我们也可以控制每一条日志的输出格式通过定义每一条日志信息的级别,我们能够更加细致地控制日志的生成过程通过一个配置文件来灵活地进行配置,而不需要修改应用的代码。分页减少数据量selsect * from user limit startIndex,pageS

  • idea2021.11.3 激活【2021免费激活】

    (idea2021.11.3 激活)JetBrains旗下有多款编译器工具(如:IntelliJ、WebStorm、PyCharm等)在各编程领域几乎都占据了垄断地位。建立在开源IntelliJ平台之上,过去15年以来,JetBrains一直在不断发展和完善这个平台。这个平台可以针对您的开发工作流进行微调并且能够提供…

  • uCOSII操作系统移植笔记

    uCOSII操作系统移植笔记笔记一:今天粗略的看了一下周立功关于uc/osII在lpc2104上的移植方面的说明,这之中印象最深的应该是irq中断和软中断方面的处理,由于arm芯片的特殊性(拥有7种处理器模式),即每种处理器模式都有自己的堆栈,这样在处理堆栈的时候就会相应的麻烦一些。在响应异常时,该移植计划在初始代码里面比在没有操作系统的初始代码多了irq的处理,移植里面的irq处理多了由汇编语言编写的对任务环境的保存,

发表回复

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

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