Browsed by
分类:DynamicProgramming

CF 543A Writing Code 完全背包问题

CF 543A Writing Code 完全背包问题

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Programmers working on a large project have just received a task to write exactly m lines of code. There are n programmers working on a project, the i-th of them makes exactly ai bugs in every line of code that he writes.

Let’s call a sequence of non-negative integers v1, v2, …, vn a plan, if v1 + v2 + … + vn = m. The programmers follow the plan like that: in the beginning the first programmer writes the first v1 lines of the given task, then the second programmer writes v2 more lines of the given task, and so on. In the end, the last programmer writes the remaining lines of the code. Let’s call a plan good, if all the written lines of the task contain at most b bugs in total.

Your task is to determine how many distinct good plans are there. As the number of plans can be large, print the remainder of this number modulo given positive integer mod.

Input

The first line contains four integers nmbmod (1 ≤ n, m ≤ 500, 0 ≤ b ≤ 500; 1 ≤ mod ≤ 109 + 7) — the number of programmers, the number of lines of code in the task, the maximum total number of bugs respectively and the modulo you should use when printing the answer.

The next line contains n space-separated integers a1, a2, …, an (0 ≤ ai ≤ 500) — the number of bugs per line for each programmer.

Output

Print a single integer — the answer to the problem modulo mod.

Sample test(s)
input

output

input

output

input

output

 

题目如上,根据上文动态规划建模的思路 ,来考虑这个问题,先把上文的建模思路放在下面:

先构造问题对应的过程 ,每个过程都是选出一个人,这个人有两种让这个人写一定行数的代码然后保证bug数小于最多允许的bug数,或者不让这个人写代码.

然后考虑这个问题的最后一步,对于最后一个程序员 ,我们有两种选择,一种是不让他写代码,另一种是让他写r行代码,因而这个问题的状态转移方程可以写为下式:

设dp[i][j][k] 表示前i个程序员写j行代码产生恰好k个错误的情况数

则 dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-r][k-r*a[i]]  (r>0) 可以看出这是一个完全背包问题,根据背包九讲里的优化方式,完全背包问题可以优化时间复杂度.

采用将01背包的循环改为正序的方法即可以适用与完全背包问题.

另外此题如果开500*500*500的longlong数组的话会MLE 需要滚动数组

AC代码如下

动态规划建模方法

动态规划建模方法

 

转载

http://www.cnblogs.com/sdjl/articles/1274312.html

通过金矿模型介绍动态规划

对于动态规划,每一个刚接触的人都须要一段时间来理解,特别是第一次接触的时候总是想不通为什么这样的方法可行,这篇文章就是为了帮助大家理解动态规划,并通过解说主要的01背包问题来引导读者怎样去思考动态规划。本文力求通俗易懂,无异性,不让读者感到迷惑,引导读者去思考,所以假设你在阅读中发现有不通顺的地方,让你产生错误理解的地方,让你难得读懂的地方,请跟贴指出,谢谢!

—-第一节—-初识动态规划——–

经典的01背包问题是这种:

有一个包和n个物品,包的容量为m,每一个物品都有各自的体积和价值,问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时,可以得到的最大价值是多少?[对于每一个物品不可以取多次,最多仅仅能取一次,之所以叫做01背包,0表示不取,1表示取]

为了用一种生动又更形象的方式来解说此题,我把此题用还有一种方式来描写叙述,例如以下:

有一个国家,全部的国民都很老实憨厚,某天他们在自己的国家发现了十座金矿,而且这十座金矿在地图上排成一条直线,国王知道这个消息后很高兴,他希望可以把这些金子都挖出来造福国民,首先他把这些金矿依照在地图上的位置从西至东进行编号,依次为0、1、2、3、4、5、6、7、8、9,然后他命令他的手下去对每一座金矿进行勘測,以便知道挖取每一座金矿须要多少人力以及每座金矿可以挖出多少金子,然后动员国民都来挖金子。

题目补充1:挖每一座金矿须要的人数是固定的,多一个人少一个人都不行。国王知道每一个金矿各须要多少人手,金矿i须要的人数为peopleNeeded。

题目补充2:每一座金矿所挖出来的金子数是固定的,当第i座金矿有peopleNeeded人去挖的话,就一定能恰好挖出gold个金子。否则一个金子都挖不出来。

题目补充3:开採一座金矿的人完毕开採工作后,他们不会再次去开採其他金矿,因此一个人最多仅仅能使用一次。

题目补充4:国王在全国范围内仅招募到了10000名愿意为了国家去挖金子的人,因此这些人可能不够把全部的金子都挖出来,可是国王希望挖到的金子越多越好。

题目补充5:这个国家的每个人都非常老实(包含国王),不会私吞不论什么金子,也不会弄虚作假,不会说谎话。

题目补充6:有非常多人拿到这个题后的第一反应就是对每个金矿求出平均每个人能挖出多少金子,然后从高到低进行选择,这里要强调这样的方法是错的,假设你也是这样想的,请考虑背包模型,当有一个背包的容量为10,共同拥有3个物品,体积各自是3、3、5,价值各自是6、6、9,那么你的方法取到的是前两个物品,总价值是12,但明显最大值是后两个物品组成的15。

题目补充7:我们仅仅须要知道最多能够挖出多少金子就可以,而不用关心哪些金矿挖哪些金矿不挖。

那么,国王到底怎样知道在仅仅有10000个人的情况下最多能挖出多少金子呢?国王是怎样思考这个问题的呢?

国王首先来到了第9个金矿的所在地(注意,第9个就是最后一个,由于是从0開始编号的,最西边的那个金矿是第0个),他的臣子告诉他,假设要挖取第9个金矿的话就须要1500个人,而且第9个金矿能够挖出8888个金子。听到这里国王哈哈大笑起来,由于原先他以为要知道十个金矿在仅有10000个人的情况下最多能挖出多少金子是一件非常难思考的问题,可是,就在刚才听完他的臣子所说的那句话时,国王已经知道总共最多能挖出多少金子了,国王是怎样在不了解其他金矿的情况下知道最多能挖出多少金子的呢?他的臣子们也不知道这个谜,因此他的臣子们就问他了:“最聪明的国王陛下,我们都没有告诉您其他金矿的情况,您是怎样知道终于答案的呢?”

得意的国王笑了笑,然后把他最得意的“左、右手”叫到跟前,说到:“我并不须要考虑终于要挖哪些金矿才干得到最多的金子,我仅仅须要考虑我面前的这座金矿就能够了,对于我面前的这座金矿不外乎仅有两种选择,要么挖,要么不挖,对吧?”

“当然,当然”大臣们回答倒。

国王继续说道:“假设我挖取第9座金矿的话那么我如今就能获得8888个金子,而我将用去1500个人,那么我还剩下8500个人。我亲爱的左部下,假设你告诉我当我把全部剩下的8500个人和全部剩下的其他金矿都交给你去开採你最多能给我挖出多少金子的话,那么我不就知道了在第9个金矿一定开採的情况下所能得到的最大金币数吗?”

国王的左部下听后回答道:“国王陛下,您的意思是假设我能用8500个人在其他金矿最多开採出x个金币的话,那您一共就行获得 x + 8888个金子,对吗?”

“是啊,是啊……假设第9座金矿一定开採的话……”大臣们点头说到。

国王笑着继续对着他的右部下说到:“亲爱的右部下,或许我并不打算开採这第9座金矿,那么我依旧拥有10000个人,假设我把这10000个人和剩下的金矿都给你的话,你最多能给我挖出多少个金子呢?”

国王的右部下聪明地说道:“尊敬的国王陛下,我明确您的意思了,假设我回答最多能购开採出y个金币的话,那您就能够在y和x+8888之间选择一个较大者,而这个较大者就是终于我们能获得的最大金币数,您看我这样理解对吗?”

国王笑得更灿烂了,问他的左部下:“那么亲爱的左部下,我给你8500个人和其余金矿的话你能告诉我最多能挖出多少金子吗?”

“请您放心,这个问题难不倒我”。左部下向国王打包票说到。

国王高兴地继续问他的右部下:“那右部下你呢,假设我给你10000个人和其余金矿的话你能告诉我最多能挖出多少金子吗?”

“当然能了!交给我吧!”右部下同左部下一样自信地回答道。

“那就拜托给你们两位了,如今我要回到我那舒适的王宫里去享受了,我期待着你们的答复。”国王说完就開始动身回去等消息了,他是多么地相信他的两个大臣可以给他一个准确的答复,由于国王事实上知道他的两位大臣要比他聪明得多。

故事发展到这里,你是否在想国王的这两个大臣又是怎样找到让国王惬意的答案的呢?他们为什么可以如此自信呢?其实他们的确比国王要聪明一些,由于他们从国王的身上学到了一点,就是这一点让他们充满了自信。

国王走后,国王的左、右部下来到了第8座金矿,早已在那里等待他们的金矿勘測兵向两位大臣报道:“聪明的两位大臣,您们好,第8座金矿须要1000个人才干开採,能够获得7000个金子”。

由于国王仅给他的左部下8500个人,所以国王的左部下叫来了两个人,对着当中一个人问到:“假设我给你7500个人和除了第8、第9的其他全部金矿的话,你能告诉我你最多能挖出多少金子吗?”

然后国王的左部下继续问还有一个人:“假设我给你8500个人和除了第8、第9的其他全部金矿的话,你能告诉我你最多能挖出多少金子吗?”

国王的左部下在心里想着:“假设他们俩都能回答我的问题的话,那国王交给我的问题不就攻克了吗?哈哈哈!”

由于国王给了他的右部下10000个人,所以国王的右部下相同也叫来了两个人,对着当中一个人问:“假设我给你9000个人和除了第8、第9的其他全部金矿的话,你能告诉我你最多能挖出多少金子吗?”

然后国王的右部下继续问他叫来的还有一个人:“假设我给你10000个人和除了第8、第9的其他全部金矿的话,你能告诉我你最多能挖出多少金子吗?”

此时,国王的右部下同左部下一样,他们都在为自己如此聪明而感到满足。

当然,这四个被叫来的人相同自信地回答没有问题,由于他们相同地从这两个大臣身上学到了相同的一点,而两位自觉得自己一样非常聪明的大臣得意地笑着回到了他们的府邸,等着别人回答他们提出来的问题,如今你知道了这两个大臣是怎样解决国王交待给他们的问题了吗?

那么你觉得被大臣叫去的那四个人又是怎么完毕大臣交给他们的问题的呢?答案当然是他们找到了另外八个人!

没用多少功夫,这个问题已经在全国传开了,很多其它人的人找到了更很多其它的人来解决问题,而有些人却不须要去另外找两个人帮他,哪些人不须要别人的帮助就能够回答他们的问题呢?

非常明显,当被问到给你z个人和仅有第0座金矿时最多能挖出多少金子时,就不须要别人的帮助,由于你知道,假设z大于等于挖取第0座金矿所须要的人数的话,那么挖出来的最多金子数就是第0座金矿可以挖出来的金子数,假设这z个人不够开採第0座金矿,那么能挖出来的最多金子数就是0,由于这唯一的金矿不够人力去开採。让我们为这些不须要别人的帮助就行准确地得出答案的人们鼓掌吧,这就是传说中的底层劳动人民!

故事说到这里先暂停一下,我们如今又一次来分析一下这个故事,让我们对动态规划有个理性认识。

子问题:

国王须要依据两个大臣的答案以及第9座金矿的信息才干推断出最多可以开採出多少金子。为了解决自己面临的问题,他须要给别人制造另外两个问题,这两个问题就是子问题。

思考动态规划的第一点—-最优子结构:

国王相信,仅仅要他的两个大臣可以回答出正确的答案(对于考虑可以开採出的金子数,最多的也就是最优的同一时候也就是正确的),再加上他的聪明的推断就一定能得到终于的正确答案。我们把这样的子问题最优时母问题通过优化选择后一定最优的情况叫做“最优子结构”。

思考动态规划的第二点—-子问题重叠:

实际上国王也好,大臣也好,全部人面对的都是相同的问题,即给你一定数量的人,给你一定数量的金矿,让你求出可以开採出来的最多金子数。我们把这样的母问题与子问题本质上是同一个问题的情况称为“子问题重叠”。然而问题中出现的不同点往往就是被子问题之间传递的參数,比方这里的人数和金矿数。

思考动态规划的第三点—-边界:

想想假设不存在前面我们提到的那些底层劳动者的话这个问题能解决吗?永远都不可能!我们把这样的子问题在一定时候就不再须要提出子子问题的情况叫做边界,没有边界就会出现死循环。

思考动态规划的第四点—-子问题独立:

要知道,当国王的两个大臣在思考他们自己的问题时他们是不会关心对方是如何计算如何开採金矿的,由于他们知道,国王仅仅会选择两个人中的一个作为最后方案,还有一个人的方案并不会得到实施,因此一个人的决定对还有一个人的决定是没有影响的。我们把这样的一个母问题在对子问题选择时,当前被选择的子问题两两互不影响的情况叫做“子问题独立”。

这就是动态规划,具有“最优子结构”、“子问题重叠”、“边界”和“子问题独立”,当你发现你正在思考的问题具备这四个性质的话,那么恭喜你,你基本上已经找到了动态规划的方法。

有了上面的这几点,我们就行写出动态规划的转移方程式,如今我们来写出相应这个问题的方程式,假设用gold[mineNum]表示第mineNum个金矿可以挖出的金子数,用peopleNeeded[mineNum]表示挖第mineNum个金矿须要的人数,用函数f(people,mineNum)表示当有people个人和编号为0、1、2、3、……、mineNum的金矿时可以得到的最大金子数的话,f(people,mineNum)等于什么呢?或者说f(people,mineNum)的转移方程是如何的呢?

答案是:

当mineNum = 0且people >= peopleNeeded[mineNum]时 f(people,mineNum) = gold[mineNum]

当mineNum = 0且people < peopleNeeded[mineNum]时 f(people,mineNum) = 0

当mineNum != 0时 f(people,mineNum) = f(people-peopleNeeded[mineNum], mineNum-1) + gold[mineNum]与f(people, mineNum-1)中的较大者,前两个式子相应动态规划的“边界”,后一个式子相应动态规划的“最优子结构”请读者弄明确后再继续往下看。

—-第二节—-动态规划的长处——–

如今我如果读者你已经搞清楚了为什么动态规划是正确的方法,可是我们为什么须要使用动态规划呢?请先继续赞赏这个故事:

国王得知他的两个手下使用了和他同样的方法去解决交代给他们的问题后,不但没有觉得他的两个大臣在偷懒,反而非常高兴,由于他知道,他的大臣必定会找很多其它的人一起解决问题,而很多其它的人会找更很多其它的人,这样他这个聪明的方法就会在不经意间流传开来,而全国人民都会知道这个聪明的方法是他们伟大的国王想出来的,你说国王能不高兴吗?

可是国王也有一些担忧,由于他实在不知道这个“project”要动用到多少人来完毕,假设帮助他解决问题的人太多的话那么就太劳民伤財了。“会不会影响到今年的收成呢?”国王在心里想着这个问题,于是他请来了整个国家里唯一的两个数学天才,一个叫做小天,还有一个叫做小才。

国王问小天:“小天啊,我发觉这个问题有点严重,我知道事实上这能够简单的看成一个组合问题,也就是从十个金矿中选取若干个金矿进行开採,看看哪种组合得到的金子最多,或许用组合方法会更好一些。你能告诉我一共同拥有多少种组合情况吗?”

“国王陛下,假设用组合方法的话一共要考虑2的10次方种情况,也就是1024种情况。”小天思考了一会回答到。

“嗯……,假设每一种情况我交给一个人去计算能得到的金子数的话,那我也要1024个人,事实上还是挺多的。”国王好像再次感觉到了自己的方法是正确的。

国王心理期待着小才可以给它一个更好的答案,问到:“小才啊,那么你能告诉我用我的那个方法总共须要多少人吗?事实上,我也计算过,好像须要的人数是1+2+4+8+16+32+64+……,毕竟每个人的确都须要找另外两个人来帮助他们……”

不辜负国王的期待,小才微笑着说到:“亲爱的国王陛下,事实上我们并不须要那么多人,由于有非常多问题事实上是同样的,而我们仅仅须要为每个不同的问题使用一个人力便可。”

国王高兴的问到:“此话怎样讲?”

“打个例如,假设有一个人须要知道1000个人和3个金矿能够开採出多少金子,同一时候还有一个人也须要知道1000个人和3个金矿能够开採出多少金子的话,那么他们能够去询问同样的一个人,而不用各自找不同的人浪费人力了。”

国王思考着说到:“嗯,非常有道理,假设问题是一样的话那么就不须要去询问两个不同的人了,也就是说一个不同的问题仅须要一个人力,那么一共同拥有多少个不同的问题呢?”

“由于每一个问题的人数能够从0取到10000,而金矿数能够从0取到10,所以最多大约有10000 * 10 等于100000个不同的问题。” 小才一边算着一边回答。

“什么?十万个问题?十万个人力?”国王有点失望。

“请国王放心,其实我们须要的人力远远小于这个数的,由于不是每个问题都会遇到,或许我们仅须要一、两百个人力就能够解决问题了,这主要和各个金矿所须要的人数有关。” 小才立马回答到。

故事的最后,自然是国王再一次向他的臣民们证明了他是这个国家里最聪明的人,如今我们通过故事的第二部分来考虑动态规划的另外两个思考点。

思考动态规划的第五点—-做备忘录:

正如上面所说的一样,当我们遇到同样的问题时,我们能够问同一个人。讲的通俗一点就是,我们能够把问题的解放在一个变量中,假设再次遇到这个问题就直接从变量中获得答案,因此每个问题仅会计算一遍,假设不做备忘的话,动态规划就没有不论什么优势可言了。

思考动态规划的第六点—-时间分析:

正如上面所说,假设我们用穷举的方法,至少须要2^n个常数时间,由于总共同拥有2^n种情况须要考虑,假设在背包问题中,包的容量为1000,物品数为100,那么须要考虑2^100种情况,这个数大约为10的30次方。

而假设用动态规划,最多大概仅仅有1000*100 = 100000个不同的问题,这和10的30次方比起来优势是非常明显的。而实际情况并不会出现那么多不同的问题,比方在金矿模型中,假设全部的金矿所需人口都是1000个人,那么问题总数大约仅仅有100个。

非正式地,我们能够非常easy得到动态规划所需时间,假设共同拥有questionCount个同样的子问题,而每个问题须要面对chooseCount种选择时,我们所需时间就为questionCount * chooseCount个常数。在金矿模型中,子问题最多有大概people * n 个(当中people是用于开採金矿的总人数,n是金矿的总数),因此questionCount = people * n,而就像国王须要考虑是採用左部下的结果还是採用右部下的结果一样,每个问题面对两个选择,因此chooseCount = 2,所以程序执行时间为 T = O(questionCount * chooseCount) =O(people * n),别忘了实际上须要的时间小于这个值,依据所遇到的详细情况有所不同。

这就是动态规划的魔力,它降低了大量的计算,因此我们须要动态规划!

—-第三节—-动态规划的思考角度———-

那么什么是动态规划呢?我个人认为,假设一个解决这个问题的方法满足上面六个思考点中的前四个,那么这种方法就属于动态规划。而在思考动态规划方法时,后两点相同也是须要考虑的。

面对问题要寻找动态规划的方法,首先要清楚一点,动态规划不是算法,它是一种方法,它是在一件事情发生的过程中寻找最优值的方法,因此,我们须要对这件事情所发生的过程进行考虑。而通常我们从过程的最后一步開始考虑,而不是先考虑过程的開始。

打个例如,上面的挖金矿问题,我们能够觉得整个开採过程是从西至东进行开採的(也就是从第0座開始),那么总有面对最后一座金矿的时候(第9座),对这座金矿不外乎两个选择,开採与不开採,在最后一步确定时再去确定倒数第二步,直到考虑第0座金矿(过程的開始)。

而过程的開始,也就是考虑的最后一步,就是边界。

因此在遇到一个问题想用动态规划的方法去解决时,最好还是先思考一下这个过程是如何的,然后考虑过程的最后一步是如何选择的,通常我们须要自己去构造一个过程,比方后面的练习。

—-第四节—-总结——-

么遇到问题怎样用动态规划去解决呢?依据上面的分析我们能够依照以下的步骤去考虑:

1、构造问题所相应的过程。

2、思考过程的最后一个步骤,看看有哪些选择情况。

3、找到最后一步的子问题,确保符合“子问题重叠”,把子问题中不同样的地方设置为參数。

4、使得子问题符合“最优子结构”。

5、找到边界,考虑边界的各种处理方式。

6、确保满足“子问题独立”,一般而言,假设我们是在多个子问题中选择一个作为实施方案,而不会同一时候实施多个方案,那么子问题就是独立的。

7、考虑怎样做备忘录。

8、分析所需时间是否满足要求。

9、写出转移方程式。

—-第五节—-练习——-

题目一:买书

有一书店引进了一套书,共同拥有3卷,每卷书定价是60元,书店为了搞促销,推出一个活动,活动例如以下:

假设单独购买当中一卷,那么能够打9.5折。

假设同一时候购买两卷不同的,那么能够打9折。

假设同一时候购买三卷不同的,那么能够打8.5折。

假设小明希望购买第1卷x本,第2卷y本,第3卷z本,那么至少须要多少钱呢?(x、y、z为三个已知整数)。

当然,这道题全然能够不用动态规划来解,可是如今我们是要学习动态规划,因此请想想怎样用动态规划来做?

答案:

1、过程为一次一次的购买,每一次购买或许仅仅买一本(这有三种方案),或者买两本(这也有三种方案),或者三本一起买(这有一种方案),最后直到买全然部须要的书。

2、最后一步我必定会在7种购买方案中选择一种,因此我要在7种购买方案中选择一个最佳情况。

3、子问题是,我选择了某个方案后,怎样使得购买剩余的书能用最少的钱?而且这个选择不会使得剩余的书为负数。母问题和子问题都是给定三卷书的购买量,求最少须要用的钱,所以有“子问题重叠”,问题中三个购买量设置为參数,分别为i、j、k。

4、的确符合。

5、边界是一次购买就能够买全然部的书,处理方式请读者自己考虑。

6、每次选择最多有7种方案,而且不会同一时候实施当中多种,因此方案的选择互不影响,所以有“子问题独立”。

7、我能够用minMoney[j][k]来保存购买第1卷i本,第2卷j本,第3卷k本时所需的最少金钱。

8、共同拥有x * y * z 个问题,每一个问题面对7种选择,时间为:O( x * y * z * 7) =   O( x * y * z )。

9、用函数MinMoney(i,j,k)来表示购买第1卷i本,第2卷j本,第3卷k本时所需的最少金钱,那么有:

MinMoney(i,j,k)=min(s1,s2,s3,s4,s5,s6,s7),当中s1,s2,s3,s4,s5,s6,s7分别为相应的7种方案使用的最少金钱:

s1 = 60 * 0.95 + MinMoney(i-1,j,k)

s2 = 60 * 0.95 + MinMoney(i,j-1,k)

s3 = 60 * 0.95 + MinMoney(i,j,k-1)

s4 = (60 + 60) * 0.9 + MinMoney(i-1,j-1,k)

s5 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1)

s6 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1)

s7 = (60 + 60 + 60) * 0.85 + MinMoney(i-1,j-1,k-1)

—-第六节—-代码參考——

以下提供金矿问题的程序源码帮助读者理解,并提供測试数据给大家练习。

输入文件名称为“beibao.in”,由于这个问题实际上就是背包问题,所以測试数据文件名称就保留原名吧。

输入文件第一行有两个数,第一个是国王可用用来开採金矿的总人数,第二个是总共发现的金矿数。

输入文件的第2至n+1行每行有两个数,第i行的两个数分别表示第i-1个金矿须要的人数和能够得到的金子数。

输出文件仅一个整数,表示可以得到的最大金子数。

输入例子:

100 5

77 92

22 22

29 87

50 46

99 90

输出例子:

133

总结 The 9th Zhejiang Provincial Collegiate Programming Contest

总结 The 9th Zhejiang Provincial Collegiate Programming Contest

题目链接

http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=337

代码神马的还没有写完 ,先把思路放上来 等到代码写好之后再贴代码

Taxi Fare

水题,注意精度问题 求出来的两个费用都要四舍五入 如果只对最后一次进行四舍五入的话会WA

Unrequited Love

这个题是想法+STL搞 首先 根据名流问题的思想 我们可以通过O(N)的算法排除掉不可能是答案的人 最后剩下一个人判断一下他是不是喜欢宴会上的所有人即可。 具体思想如下:如果A喜欢B,那么B就不可能是Unrequited Love King or Queen (以下简称ans)反之,如果A不喜欢B 那么A就不可能是 ans 因此每次判断都会使问题的规模缩小1 这样就可以把问题规模在O(N)时间内缩小到 1,这样就只用判断一下这个人是不是ans即可,具体实现的时候 用 set存所有的喜欢关系 每个关系用一个二元组 pair<int,int>来表示,每一个名字映射到一个map<string,int>上 ,在具体实现时可以对上面的名流问题的解法进行优化,我们只需要一重循环从1—>N初值ans=1 然后去判断 如果ans不喜欢 i 或者 i喜欢ans 那么我们就更新ans 为 i 这里我们只判断了两种情况 实际上,ans 和 i之间的关系有四种 :

  1. ans喜欢i
  2. ans不喜欢i
  3. i喜欢ans
  4. i不喜欢ans

我们需要说明一下 循环中 既不满足 2 也不满足 3的i值一定不会是ans  ,很明显可以看出,这时,i和ans的关系一定是 1 4的任意一种,而这两个关系的任何一个 都说明了 i不可能是ans 所以我们这时候不去更新ans是正确的。因此这个算法的具体实现也没有问题了。 然后最后得到的ans我们还要判断一下他是不是喜欢所有人 。

—ps 这个题和性别无关哦~~~  heterosexuals 男男之间也可以互相喜欢哒 。有些人没看到这个地方以为是只有异性之间才可以互相喜欢 那么就会把问题搞错搞复杂

Count the Trees

还是用hash的思想来稿 具体实现可以用map 这个题让我们判断有多少相同的子树,每个子树的样式可以用一个标号唯一确定 一棵树总共有n棵子树,同时 每个子树的结构可以用它的左右子树来唯一表示 ,这样的话 就建立了对应关系 我们用 pair<a,b>表示一个左子树样式标号为a右子树样式标号为b的树,用 map<pair<a,b> k>表示 这棵树的样式标号映射为k 然后再用一个一维数组tree[1-N]保存每颗子树的样式标号 ,特殊处理叶子节点 叶子节点的样式标号全部为 0 然后map[pair<-1,-1>]=0即可。通过上面的方式,我们建立起第一棵树之后,用同样的方式建立第二棵树,并且每次进行合并操作的时候遇到一个pair 就去左边查询是否存在这个pair 存在的话 取出它的标号 然后去tree这个数组里循环一次,统计所有样式标号与之相同的,这些子树的结构都与其同构。然后输出总的同构树即可。

Draw Something Cheat

水题,用二维数组 a[N] [26]保存一下第i 次输入中 每个字母出现的次数(0–25表示字母) 并且,找出每个字母出现的最少次数 按照顺序输出即可

Tunnel Network

这个题属于数学题 如果不知道Cayley公式和Prufer编码这个题真的就几乎无解了,Prufer编码的详细知识可以参看这个文章,matrix巨巨写的。下面只说明本题的思路,这个题里面N个节点的图 有S个 联通分量而且 第i个联通分量一定有i这个节点,而且判断联通分量是否相同时和标号有关 即 10 11 联通 与 9 8 联通是不同的两个情况 ,我们要求的是总共有多少种可能的连通方式。我们给图中加一个根节点 0 并让 0与每个联通分量相连,这样的话 就构成了一个由n+1个节点构成的有序号的无向树,这里需要改变一下Prufer编码的方式 我们让Prufer编码从节点标号最大的叶子开始删除 其它的不变,显然这样的Prufer编码还是与无向树一一对应,然后 注意到 这个Prufer序列的最后s-1个元素一定是0 (因为最后s-1个删除的节点一定是s—–2这些节点) 然后 倒数第s个元素一定是 1–s中的某一个值 (因为在这棵树变成只含有0—–s这些节点的树之前的状态,一定有一个叶子节点与1—s中的某一个相连,则删除它的时候会添加进来1—s中的某个值) 然后 问题就解决了 根据Prufer公式 本题中有N+1个节点 ,Prufer序列的长度为 N+1-2=N-1,排除掉有特殊情况的Prufer编码序列中最后S位 剩下的n-1-s位每一位都可以取1—N的任意值构成Prufer序列 所以 总数为 N^(N-S-1)*S ,然后用快速幂搞一下即可

Find the Marble

DP到现在为止知识储备还几乎是零,队友讲解了这个题之后总算明白了 这个题由于求概率的话 数字小到double会丢精度,因而我们存频数 并且使用三维来存储状态

dp[n][m][k]表示的是: 第m次交换时,看到k次交换的情况下 球在n号杯子里的频数,它的值就是 dp[n][m-1][k]+dp[CC][m-1][k-1]  ,即 前m-1次交换时,看到了k次 (即这次没看到)  看到球在n号盒子里的频数,以及 前m-1次交换时,看到了k-1次 (即这次看到了)看到球在CC号盒子里的频数 (这里有一个判断 如果 第m-1次交换的序列中 有 (n,CC) 或 (CC,n)这样的交换 ,那么球所在的盒子就会变,否则的话,球所在的盒子还是n 所以 CC要么是 n 要么是第m-1次交换的另一个杯子的编号) 。

初始状态 要把 dp[s][0][0]置为1 其它全部置零即可 然后循环的时候,三重循环的顺序如下:

i=1 To m

j=1To i

k=1 To n

然后 最后找出 dp[1–N][m][k]中的最大值对应的N 就是我们要求的结果

Lazy Salesgirl

广告位出租…

Lazier Salesgirl

广告位出租… 简单的模拟 不过我还没做

Signal Detection

广告位出租…

Modular Inverse

本来是扩展欧几里德 不过数据很水,用一下暴力就解决了 注意特殊情况的判断 m=1的时候会有特殊情况

Yet Another Story of Rock-paper-scissors

这个故事告诉我们 做人要心怀善心为他人着想。

在题目描述下 每次都是女的会赢,所以只要输出一个字串即可

POJ 1018 DP入门

POJ 1018 DP入门

http://blog.csdn.net/xiaoxiaoluo/article/details/7787168      代码完全参考这个blog  刚开始学习DP真是很艰难阿,  题目如下:

 

We have received an order from Pizoor Communications Inc. for a special communication system. The system consists of several devices. For each device, we are free to choose from several manufacturers. Same devices from two manufacturers differ in their maximum bandwidths and prices.
By overall bandwidth (B) we mean the minimum of the bandwidths of the chosen devices in the communication system and the total price (P) is the sum of the prices of all chosen devices. Our goal is to choose a manufacturer for each device to maximize B/P.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by the input data for each test case. Each test case starts with a line containing a single integer n (1 ≤ n ≤ 100), the number of devices in the communication system, followed by n lines in the following format: the i-th line (1 ≤ i ≤ n) starts with mi (1 ≤ mi ≤ 100), the number of manufacturers for the i-th device, followed by mi pairs of positive integers in the same line, each indicating the bandwidth and the price of the device respectively, corresponding to a manufacturer.

Output

Your program should produce a single line for each test case containing a single number which is the maximum possible B/P for the test case. Round the numbers in the output to 3 digits after decimal point.

Sample Input

Sample Output

这个题目也可以不用dp来做,不过现在既然练习的是dp这里就只给出dp如何做

思路是这样的,因为我们要找最大的B/sum P那么无论对于哪一个B ,该状态下的sumP 应该最小, 然后 枚举所有的最终态,找到最大的B/sumP 既是正确答案,

有一点小问题要注意一下 输出的问题,输出浮点数的时候不要用%.nlf  用%.nf前者在一些编译器上会概率性出错  尤其是POJ23333333

我们用dp[i][j]来表示选前i件物品 且 最小带宽为j的情况下的最小sumP

这样状态转移方程就可以表示为

 

根据这个状态转移方程 其实可以理解这个算法了,就是遍历所有的从 0 —-maxb的dp数组然后对当前选的组别进行dp  由于带宽不是连续的 因此从 0—maxb 中 有很多无意义的带宽值 这些值就用 -1 这个不能被正常计算取到的值进行标记 ,然后 选第一组物品的时候 对dp数组进行初始化赋值,从第二轮开始,每一轮dp都是先看这个数组里这里的dp[i][minb]是否算过了,如果没有算过,就直接用上一步dp[i-1][j]的值进行处理 否则 要比较当前的值和 dp[i-1][j]+p[k] 的大小 ,取小的那个

 

代码如下:

上面的状态转移方程和这里用的字母都一致对应

DP题目列表

DP题目列表

转载非原创

※最近更新:Poj斜率优化题目

1180,2018,3709

 

列表一:经典题目题号:
容易:
1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178,

1179, 1189, 1191,1208, 1276, 1322, 1414, 1456, 1458,

1609, 1644, 1664, 1690, 1699, 1740, 1742, 1887, 1926,

1936, 1952, 1953, 1958, 1959, 1962, 1975, 1989, 2018,

2029, 2039, 2063, 2081, 2082, 2181, 2184, 2192, 2231,

2279, 2329, 2336, 2346, 2353, 2355, 2356, 2385, 2392, 2424,
不易:
1019, 1037, 1080, 1112, 1141, 1170, 1192, 1239,

1655, 1695, 1707, 1733(区间减法加并查集),

1737, 1837, 1850, 1920(加强版汉罗塔), 1934(全部最长公共子序列), 1964(最大矩形面积,O(n*m)算法), 2138, 2151, 2161, 2178,
推荐:
1015, 1635, 1636(挺好的), 1671, 1682, 1692(优化), 1704, 1717, 1722, 1726, 1732, 1770,

1821, 1853, 1949, 2019, 2127, 2176, 2228, 2287, 2342, 2374, 2378, 2384, 2411
列表二:完整DP题目列表

1015 Jury Compromise
1029 False coin
1036 Gangsters
1037 A decorative fence
1038 Bugs Integrated, Inc.
1042 Gone Fishing
1050 To the Max
1062 昂贵的聘礼
1074 Parallel Expectations
1080 Human Gene Functions
1088 滑雪
1093 Formatting Text
1112 Team Them Up!
1141 Brackets Sequence
1143 Number Game
1157 LITTLE SHOP OF FLOWERS
1159 Palindrome
1160 Post Office
1163 The Triangle
1170 Shopping Offers
1178 Camelot
1179 Polygon
1180 Batch Scheduling
1185 炮兵阵地
1187 陨石的秘密
1189 钉子和小球
1191 棋盘分割
1192 最优连通子集
1208 The Blocks Problem
1239 Increasing Sequences
1240 Pre-Post-erous!
1276 Cash Machine
1293 Duty Free Shop
1322 Chocolate
1323 Game Prediction
1338 Ugly Numbers
1390 Blocks
1414 Life Line
1432 Decoding Morse Sequences
1456 Supermarket
1458 Common Subsequence
1475 Pushing Boxes
1485 Fast Food
1505 Copying Books
1513 Scheduling Lectures
1579 Function Run Fun
1609 Tiling Up Blocks
1631 Bridging signals 2分+DP NLOGN
1633 Gladiators
1635 Subway tree systems
1636 Prison rearrangement
1644 To Bet or Not To Bet
1649 Market Place
1651 Multiplication Puzzle
1655 Balancing Act
1661 Help Jimmy
1664 放苹果
1671 Rhyme Schemes
1682 Clans on the Three Gorges
1690 (Your)((Term)((Project)))
1691 Painting A Board
1692 Crossed Matchings
1695 Magazine Delivery
1699 Best Sequence
1704 Georgia and Bob
1707 Sum of powers
1712 Flying Stars
1714 The Cave
1717 Dominoes
1718 River Crossing
1722 SUBTRACT
1726 Tango Tango Insurrection
1732 Phone numbers
1733 Parity game
1737 Connected Graph
1740 A New Stone Game
1742 Coins P
1745 Divisibility
1770 Special Experiment
1771 Elevator Stopping Plan
1776 Task Sequences
1821 Fence
1837 Balance
1848 Tree
1850 Code
1853 Cat
1874 Trade on Verweggistan
1887 Testing the CATCHER
1889 Package Pricing
1920 Towers of Hanoi
1926 Pollution
1934 Trip
1936 All in All
1937 Balanced Food
1946 Cow Cycling
1947 Rebuilding Roads
1949 Chores
1952 BUY LOW, BUY LOWER
1953 World Cup Noise
1958 Strange Towers of Hanoi
1959 Darts
1962 Corporative Network
1964 City Game
1975 Median Weight Bead
1989 The Cow Lineup
2018 Best Cow Fences
2019 Cornfields
2029 Get Many Persimmon Trees
2033 Alphacode
2039 To and Fro
2047 Concert Hall Scheduling
2063 Investment
2081 Recaman’s Sequence
2082 Terrible Sets
2084 Game of Connections
2127 Greatest Common Increasing Subsequence
2138 Travel Games
2151 Check the difficulty of problems
2152 Fire
2161 Chandelier
2176 Folding
2178 Heroes Of Might And Magic
2181 Jumping Cows
2184 Cow Exhibition
2192 Zipper
2193 Lenny’s Lucky Lotto Lists
2228 Naptime
2231 Moo Volume
2279 Mr. Young’s Picture Permutations
2287 Tian Ji — The Horse Racing
2288 Islands and Bridges
2292 Optimal Keypad
2329 Nearest number – 2
2336 Ferry Loading II
2342 Anniversary party
2346 Lucky tickets
2353 Ministry
2355 Railway tickets
2356 Find a multiple
2374 Fence Obstacle Course
2378 Tree Cutting
2384 Harder Sokoban Problem
2385 Apple Catching
2386 Lake Counting
2392 Space Elevator
2397 Spiderman
2411 Mondriaan’s Dream
2414 Phylogenetic Trees Inherited
2424 Flo’s Restaurant
2430 Lazy Cows
2915 Zuma
3017 Cut the Sequence
3028 Shoot-out
3124 The Bookcase
3133 Manhattan Wiring
3345 Bribing FIPA
3375 Network Connection
3420 Quad Tiling ?

 

Virtual Contests #1