我一直在PEG Online Judge中遇到一个问题,称为Dominos,你可以在这里找到:
http://wcipeg.com/problem/domino
简要描述:
我们给出了一个水平排列的不同高度和位置的多米诺骨牌列表.位置x的高度为h的多米诺骨牌,一旦被推向右侧,将在x + 1,x + 2,...,x + h位置向右敲击所有多米诺骨牌.相反,推向左侧的同一多米诺骨牌会将所有多米诺骨牌敲到位置x-1,x-2,...,xh向左.
推翻所有多米诺骨牌的最小推动次数是多少？
例:
|
| |
| | | | | |
1 2 3 4 5 6 7 8
答案是2.将多米诺骨牌推向位置1向右,多米诺骨牌位于第8位向左.
约束:
输入以单个整数N≤100,000(多米诺骨牌的数量)开始,后跟N对整数.每对整数代表多米诺骨牌的位置和高度.(1≤位置≤1,000,000,000,1≤≤1,000,000,000)两个多米诺骨牌都不在同一地点.
内存限制:64mb
时间限制:1.00s
注意:60%的测试数据的N≤5000.
有一种强力解决方案只能解决60%的输入问题.
看起来应该有一个使用动态编程的子二次或甚至线性解决方案,以便获得最大输入大小的AC.
任何提示将不胜感激.
作者有一个提示,我不太明白,以防它有用:
创建一个递归函数f(n),它提供推翻前n个多米诺骨牌所需的最小移动次数.
现在,您如何将f(n)与f的先前值相关联？Domino #n有两个选择:向左移动(在这种情况下它会推翻其他多米诺骨牌)或向右移动(在这种情况下,左边的另一个多米诺骨牌将其翻倒).尝试从那里工作.
谢谢!