楼主:
Moderator (ㄒㄒㄒㄒㄒㄒㄒㄒㄒㄒㄒx)
2020-01-24 00:47:29: http://0rz.tw/fLPOZ
: 题目PDF如上
又来问这张考卷>"<
想请问题号V.a.2
题目说要用O(n^2)的时间
以一个双边queue(dequeue)制造max alternative sum
作者: cossetannie (paa) 2020-01-24 01:34:00
我是先选最大的pop之后再挑最小的pop 然后重复 刚好O(n^2) 你那样的作法也是可以不过题目的input应该是一个deque吧?
题目说要对given deque做 你这样的做法感觉破坏了原本的deque 而且也不一定能够在原本的deque做出这样的sequence？一楼的做法不就是题目给的greedy吗？
作者:
FRAXIS (喔喔)
2020-01-24 12:34:00这题应该要 DP 吧
作者: cossetannie (paa) 2020-01-24 13:30:00
我是挑整个deque的最大最小 题目是看两个end的元素先取较大的再取较小的
作者:
mathtsai (mathtsai)
2020-01-25 02:58:00定义dp[a][b]为从a到b所能得的最大alternative sumdp[a][b] = max{in[a]+dp[a+1][b], in[b]+dp[a][b-1]}表格: n^2格 ， 每格要查另外两格得到答案 时间O(n^2)_recurrence、boundary condition还要看现在要加还是减写的时候写仔细点别漏掉就好题目的deque是给定的，不能改变里面的顺序a的话 随便给个反例就行了 ex. {5,3,1,2,4}
作者:
FRAXIS (喔喔)
2020-01-25 12:32:00你这样定义 dp[a][b] 要怎么考虑 alternative?
作者:
mathtsai (mathtsai)
2020-01-25 14:48:00楼上的疑问是...？定义不清楚吗？看dp[a][b]是第几次要取的数字 来决定这次要加还是减要减的话 在上面in[a]、in[b]前面加上"-"就好