uva10003CuttingSticks简单区间dp

作者:网络    软件教程库   2020-05-12

// uva 10003 cutting sticks 区间dp
// 经典的区间dp
// dp(i,j)表示切割小木棍i-j所需要的最小花费
// 则状态转移为dp(i,j) = min{dp(i,k) + dp(k,j) + a[j]-a[i])
// 其中ki  kj
// a[j] - a[i] 为第一刀切割的代价
// a[0] = 0,a[n+1] = l;
// dp数组初始化的时候dp[i][i+1]的值为 0,这表示
// 每一段都已经是切割了的,不需要在切割了,其他的
// 都为inf,采用记忆化搜索,很简单的过了
// 
//
// 刚开始的时候,我以为dp[i][i+1]=l的,交了一发,wa了
// 然后仔细的想了一下状态,发现状态(i,i+1)本身表示中间已经没有切割点了,直接
// 赋值为0.然后就过了。
// 这道题学到了:初始化的条件很重要。
// 哎,继续练吧。。。。

#include algorithm
#include bitset
#include cassert
#include cctype
#include cfloat
#include climits
#include cmath
#include complex
#include cstdio
#include cstdlib
#include cstring
#include ctime
#include deque
#include functional
#include iostream
#include list
#include map
#include numeric
#include queue
#include set
#include stack
#include vector
#define ceil(a,b) (((a)+(b)-1)/(b))
#define endl #39;\n#39;
#define gcd __gcd
#define highbit(x) (1ull(63-__builtin_clzll(x)))
#define popcount __builtin_popcountll
typedef long long ll;
using namespace std;
const int mod = 1000000007;
const long double pi = acos(-1.l);

templateclass t inline t lcm(const t a, const t b) { return a/gcd(a, b)*b; }
templateclass t inline t lowbit(const t x) { return x-x; }
templateclass t inline t maximize(t a, const t b) { return a=abb:a; }
templateclass t inline t minimize(t a, const t b) { return a=aba:b; }

const int maxn = 1008;
int a[maxn];
int n,l;
int d[maxn][maxn];
const int inf = 0x3f3f3f3f;


void init(){
	scanf(%d,n);
	for (int i=1;i=n;i++)
		scanf(%d,a[i]);
	for (int i=0;i=n+1;i++)
		for (int j=0;j=n+1;j++)
			d[i][j] = inf;
	for (int i=0;in+1;i++)
		d[i][i+1] = 0;
	a[0] = 0;
	a[n+1] = l;
}

int dp(int i,int j){
	if (d[i][j]!=inf)
		return d[i][j];
	int ans = d[i][j];
	for (int k=i+1;kj;k++)
		ans = min(ans,dp(i,k)+dp(k,j)+a[j]-a[i]);
	return ans;
}

void solve(){
	printf(the minimum cutting is %d.\n,dp(0,n+1));
}

int main() {
	//freopen(g:\\code\\1.txt,r,stdin);
	while(scanf(%d,l)!=eof){
		if (l==0)
			break;
		init();
		solve();
	}
	return 0;
}

uva 10003 cutting sticks 简单区间dp

原文地址:http://blog.csdn.net/timelimite/article/details/45423013

软件教程库 原文链接:https://www.itjcku.com/9999/1091353.html

阅读全部内容


Tags:简单区间

返回首页



推荐内容

Go的语言特性总结

写在前面: 近来关于对golang的讨论有很多,七牛的几个大牛们也断定go语言在未来将会快速发展,并且很可能会取代ja ...

golang控制channel的出入口

golang控制channel的出入口 我们常常使用channel来在多个goroutine之间做数据通讯,但是cha ...

UVA10479TheHendrieSequence规律

题目大意:一个序列,刚开始由0变到了1,接着往后一个个变化下去 变化的规则是,如果当前数是k,就在这个序列的最后面加上 ...

在不是Activity类中调用Toast和Dialog

有时候我们需要在非activity类中处理一些逻辑,显示toast对话框或者是弹出一个dialog,但是在非activi ...

查询Oraclesql语句中绑定变量值的方法

alter session set nls_date_format = #39;yyyy-mm-dd,hh24:mi:s ...

Hdoj1588GaussFibonacci【矩阵快速幂】

gauss fibonacci time limit: 1000/1000 ms (java/others) m ...

Hdoj5195DZYLovesTopologicalSorting【拓扑】+【线段树】

dzy loves topological sorting time limit: 4000/2000 ms (jav ...

【转自mos文章】使用单条sql来查询出awr中的syatemstatistics

使用单条sql来查询出awr中的syatem statistics 参考自: how to monitor system ...

I.MX6Q(TQIMX6Q/TQE9)学习笔记——新版BSP之u-boot移植

前段时间就开始学习i.mx6q了,但是最近工作实在是忙,间断了一些时间了。为了提高移植效率,还是考虑移植freescal ...

eclipse应用技巧

最近发现eclipse作为ide还是有很多值得探索的使用技巧的,转载一下他人整理好的资源以做分享。 快捷键的使用,加速 ...

Mysql创建数据库的排序规则中文选择哪种编码

mysql中文编码 mysql创建数据库的排序规则 中文 选择哪种编码原文地址:http://blog. ...

线性表简述

一、简单实现增,删,改、查 package datatructs; /** * 表接口 */ public int ...

android测试本地服务调试流程

我今天调试的整个过程 1,安卓发现连不上本地的tomcat 2,使用浏览器直接尝试,发现可以连上 3,怀疑是安卓app和 ...

设计模式1

静态工厂模式,工厂方法模式,抽象工厂模式 工厂方法改进了添加新产品时,静态工厂不满足的开-闭原则;而抽象工厂满足了当产品 ...

c语言文件操作总结

#includelt;stdio.hgt; /********************************** ...

(c#)如果添加的字段中已经有了身份证号码,则年龄和性别和出生年月可得

//把界面文本框里面的身份证号进行提取,以二代身份证为例 model.ecardid = txt_cardno. ...

Scrum时间估算

在新公司里,不懂软件工程的产品经理经常逼迫研发人员作出很不靠谱的时间估算。常见场景有下面这些: 需求未细化的情况下要求给 ...

C++11中uniforminitialization和initializer_list

c++11中出现了uniform initialization的概念: int a1 = {1};//ok int a ...

关于Scrum

最近某些产品经理发出下两周的工作计划的时候,喜欢带上sprint这个字眼,看上去貌似是要走敏捷开发这一套,只可惜,我觉得 ...

输入输出简单解释

;汇编指令,表示程序将被汇编成能在intel386系列及以上的计算机上运行.386;model flat 表明程序使用保 ...

2015第18周五问题即机会

问题即机会,当一切问题都不存在的时候,请问你的机会在哪里? 你能达到怎样的境界,取决于你怎样认识这个世界。对于问题,有人 ...

solr配置方案

http://www.sjsjw.com/kf_cloud/article/44_5945_1823.asp cento ...

什么是二维码?

二维码,业界当然是人人听说,人人用过。 这个话题,我倒是百感交集,我一直认为,我有一种二维码情节。 一方面, 我自认 ...

1475:方格取数

1475: 方格取数 time limit:5 secmemory limit:64 mbsubmit:578solv ...

敏捷开发宣言(一)

原文: inpiduals and interactionsover processes and tools worki ...

(C#)一个项目的配置和增删改查

一、windows窗体项目环境配置步骤 1.文件mdash;gt;新建mdash;gt;项目mdash;gt;windo ...

比例简化

题目描述description 在社交媒体上,经常会看到针对某一个观点同意与否的民意调查以及结果。例如,对某一观点表示 ...

sockaddr和sockaddr_in的区别

struct sockaddr和struct sockaddr_in这两个结构体用来处理网络通信的地址。 在各种系统调用 ...

基于Html5的智能家居手机客户端设计(一)——找到openhab的rest

今天开始我的毕业设计,基于html5的智能家居手机客户端设计。挑剔了好久,终于找到我可以使用国外开源项目智能家居核心 ...

阅读《大道至简--软件工程实践者的思想》有感(3)

阅读完《大道至简--软件工程实践者的思想》,明白了软件与程序的区别,《战国策-秦策》中的那句话,王不如远交而近攻, ...


本网站部分内容来自互联网,版权归原作者所有,文章内容仅代表原作者个人观点。如有侵权请联系我们删除 电子邮件 itjcku@foxmail.com