动态规划优化的一个问题、Pascal

来源：蜘蛛抓取(WebSpider) 时间：2012-06-05 01:29 标签： 动态规划优化
排队买票问题PASCAL动态规划_百度知道
排队买票问题PASCAL动态规划
T[j]+T[j+1],队伍中相邻的两位歌迷（第j个人和第j+1个人）也可以由其中一个人买两张票。如果前i个人买票的最优买票方式一确定，T[j]和R[j]；现在要决定F(i)需要考虑两种情况，加快整个售票的进程;=i&lt，则前i-1个人的买票方式也一定是最优的,求使每个人都买到票的最短时间和算法，则这两位歌迷买两张票的时间变为R[j]，一人面一张票，而另一个人就可以不用排队了，现有n个歌迷排队买票，比如第i-1个人买一张票，假设第i位歌迷买一张票需要时间T[i](1&lt，一人每次只能买一张票。现在给出 n 一场演唱会即将举行，而售票处规定;=n),这样做就可以缩短后面歌迷的等待时间。步骤1，即所需最短时间：用F（i）表示前i个人买票的最优方式,且有R[j]&lt
提问者采纳
{i = 2 ~ n}初值 f[0] ; f[1] := 0:= t[1];完整的代码就不需要了吧状态转移方程是 f[i] := min(f[i - 1] + t[i], f[i - 2] + r[i - 1])
我连动态规划都没学过，你说要不要
maxn = 1000;
var i, j, n :
f, t, r : array[0..maxn]
function min(a, b : longint) :
begin if a & b then exit(a); exit(b);
readln(n);
for i := 1 to n do read(t[i]);
for i := 1 to n - 1 do read(r[i]);
f[0] := 0; f[1] := t[1];
for i := 2 to n do
f[i] := min(f[i - 1] + t[i], f[i - 2] + r[i - 1]);
writeln(f[n]);
其他类似问题
pascal的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁问题补充&&
划分阶段21。选择状态3。确定决策并写出状态转移方程4
yukunlinykl &
•回答
•回答
•回答
•回答
•回答
我认为做的题要做的多 但对于某个具体的问题 如果这个类型没有碰到 想要求出状态转移方程 关键是要看这个问题的重叠子问题 动规的核心是不做重复的问题 知道了重叠的子问题 就知道动规存的是什么了 动规的方程就容易想了
没有捷径，多看例题。多理解。
猜你感兴趣
服务声明： 信息来源于互联网，不保证内容的可靠性、真实性及准确性，仅供参考，版权归原作者所有！Copyright &
Powered by谁能教教我一道动态规划呀，快烦死我了==_pascal吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：7,028贴子：
谁能教教我一道动态规划呀，快烦死我了==收藏
快试试吧，可以对自己使用挽尊卡咯~◆◆
本人刚学动态规划，所以很弱智的想问一道高手们觉得弱智的题。
就是关于最长公共子串的，下面请听题
胖男孩&
(fatboy.pas/c/cpp)&【问题描述】&&&&&麦克正如我们所知的已快乐地结婚，在上个月他胖了70磅。因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。
&&&&每晚麦克都详细地描述那一天他所吃的所有东西，但有时当他只想按一次某键时往往会按了不止一次，并且他的胖手指还会碰到他不想要按的键，麦克也知道自己的手指有问题，因此他在打字的时候很小心，以确保每打一个想要的字符时误打的字符不超过3个，误打的字符可能在正确字符之前也可能在其之后。
当斯拉夫克多次收到读不懂的电子邮件后，他总是要求麦克将电子邮件发3遍，使他容易读懂一点。
编写程序，帮助斯拉夫克根据他所收到的三封电子邮件求出麦克可能写出的最长的信。
【输入文件】&输入文件fatboy.in包含了三行文本。每一行文本包括麦克信件的一种版本。其中所有的字符都由英文字母表中的小写字母组成并且不超过100个。
【输出文件】&输出文件fatboy.out中第一行即唯一的一行数据应该包含斯拉夫克根据所收到的电子邮件推测出的最长信件。你可以相信问题一定有解，但解不一定是唯一的。
【输入样例】&cecqbhvaiaedpibaluk
cabegviapcihlaaugck
adceevfdadaepcialaukd
【输出样例】&cevapiluk
dp[i,j,k]=max{length(
dp[i-1,j,k]
dp[i,j-1,k]
dp[i,j,k-1]
dp[i-1,j-1,k]
dp[i-1,j,k-1]
dp[i,j-1,k-1])
(not&(a[i]=b[j]=c[k]))
dp[i-1,j-1,k-1]+a[i]
(a[i]=b[j]=c[k])
}
快试试吧，可以对自己使用挽尊卡咯~◆◆
orz...By&Ceeji(这次发表验证码是9NNB)
快试试吧，可以对自己使用挽尊卡咯~◆◆
ceeji你无处不在啊。。。orz
快试试吧，可以对自己使用挽尊卡咯~◆◆
可是怎么输出字符串，我只会输出它的长度
登录百度帐号推荐应用
为兴趣而生，贴吧更懂你。或动态规划36讲_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
文档贡献者
评价文档：
喜欢此文档的还喜欢
动态规划36讲
语​言
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
大小：126.55KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢动态规划 - 求解二项式系数(自顶向下,自底向上) - 爪哇哥的爪哇岛 - ITeye技术网站
博客分类：
1. 动态规划 备忘录法
备忘录方法采用自顶向下方式,为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。
在非边界条件下,每次求解子问题时,先查找备忘录.
若子问题已经求解过了,直接取出子问题的解;若未求解过,则求解并保存到备忘录中.
此处的备忘录就是一个存储数据的容器.
@author: jarg
@TODO 动态规划 - 备忘录法 求解二项式系数
/* 求解二项式系数 */
public static int Binomial(int n,int m)
/* 边界条件 */
if(n==m || m==0)
int date = readDate(n,m);
if(date&0)
子问题已经计算过
读取保存在备忘录中的数据
子问题未计算过
解出子问题,将数据保存在备忘录中
int result = Binomial(n-1,m) + Binomial(n-1,m-1);
writeDate(n,m,result);
/* 从备忘录中读取数据 */
public static int readDate(int n,int m)
for(int i=0;i&demo.size();i++)
Map&String,Integer& date = new HashMap&String,Integer&();
date = demo.get(i);
if(date.get("" + n + m) != null)
return date.get("" + n + m);
/* 向备忘录中写入数据 */
public static void writeDate(int n,int m,int value)
Map&String,Integer& date = new HashMap&String,Integer&();
date.put("" + n + m,value);
demo.add(date);
2. 动态规划 迭代法:
迭代法采用自底向上方式,保存已求解的子问题,需要时取出,消除对某些子问题的重复求解.
Pascal三角形:
说明: 在非边界的情况下,二项式系数=上一行同列数值+上一行同列前一个数值.
为了节省空间,根据n的大小,定义长度为n+1的整型数组,用以存储子问题的解.
从后往前计算图中二项式系数的解,完成后,将问题解存储在数组中对应的列标号位置.
@author: jarg
@TODO: 动态规划 - 求解二项式系数
/* 求二项式系数 */
public static int binomial(int n, int m)
int value[] = new int[n+1];
for(int i=0;i&=n;i++)
value[i] = 1;
/* 边界条件m=0,n=m的情况 */
for(int j=i-1;j&0;j--)
value[j] = value[j] + value[j-1];
return value[m];
描述: 完整代码
下载次数: 5
yeshaoting
浏览: 274868 次
来自: 北京
竟然还有马
我刚也遇到这个问题，然后也把默认端口改成了1433，只差最后没 ...
kingbinchow 写道
最近的爪哇岛 没有什么货进项呀 ...
最近的爪哇岛 没有什么货进项呀！

我要回帖

更多关于 动态规划优化 的文章

 

随机推荐