CODE, ARCHITECTURE & AI

dynamic programming.

33 篇记录保持好奇,慢慢积累

双子塔

【Description】 为了纪念9.11,大家决定重修双子塔. 材料是立方体的水晶{这么阔!}, 问对于给定的水晶,可否修起等高的 双子塔(高度<=2000). 【Input】 第一个数字N(100000以内)代表水晶的个数. 接下来N行每行一个数(<1000),代表水晶体的边长. 【Output】 如果可以建成就输入高度,不能建则输出0. 【Sampl…
继续阅读 ↗

装箱问题

描述 Description 有一个箱子容量为v(正整数,o≤v≤20000),同时有n个物品(o≤n≤30),每个物品有一个体积 (正整数)。要求从 n 个物品中,任取若千个装入箱内,使箱子的剩余空间为最小。 输入格式 Input Format 第一行,一个整数,表示箱子容量; 第二行,一个整数,表示有n个物品; 接下来n行,分别表示这n个物品的各自体积。…
继续阅读 ↗

晴天小猪历险记之Hill

在很久很久以前,有一个动物村庄,那里是猪的乐园(^_^),村民们勤劳、勇敢、善良、团结…… 不过有一天,最小的小小猪生病了,而这种病是极其罕见的,因此大家都没有储存这种药物。所以晴天小猪自告奋勇,要去采取这种药草。于是,晴天小猪的传奇故事便由此展开…… 【描述 Description】 这一天,他来到了一座深山的山脚下,因为只有这座深山中的一位隐者才知道这种…
继续阅读 ↗

邮局问题 vijos1242(和以前的pku上的应该是一样的.)

/* 动态规划。 将n个村庄按坐标递增依次编号为1,2,……,n,各个邮局的坐标为a[1..n], 状态表示描述为:f[i,j]表示在前i个村庄建立j个邮局的最小距离和。所以,f[n,p]即为问题的解, 且状态转移方程和边界条件为: f[j,1]=w[1,j]; f[i,j]=min{f[k,j - 1]+w[k+1,i]}; (i≤j, j - 1≤k≤i…
继续阅读 ↗

Post Office pku1160 邮局

package pku1160; /*在一条高速公路边上有V个村庄,用一条坐标轴来描述这条公路,每个村庄的坐标各不相同, * 且都是整数。两个村庄间的距离用他们的坐标值差的绝对值表示。现在要在这些村庄中选 * 出P个建立邮局,邮局建立在村庄里,每个村庄使用离他最近的那个邮局。求一种建设方案, * 使得所有村庄到各自所使用的邮局的距离总和最小。 * * 算法:…
继续阅读 ↗

合唱队形

【问题描述】 N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK, 则他们的身高满足T1<... Ti+1>…>TK(1<=i<=K)。 你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下…
继续阅读 ↗

滑雪 pku1088 动态规划

【Description】 Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 5 16 17 18 19 6 15 24 25…
继续阅读 ↗