18 2016-09 HDU 5900 QSC and Master (区间dp) 紫杉 区间DP 2016-09-18 2,409 题目链接:点我~~ 题意:n 个pair<int , int>,每次可以选相邻两个pair。如果他们的first不互质就可以把它们都删掉,并且获得second之和的分数,问最大得分。 思路:设f[i][j]为[i,j]这段区间能取得的最大得分,转移就是不取左边/不取右边/断开拼起来/取两边,其中取两边需要中间能取干净才能取。复杂度 O(n^3)。... 区间DP区间DP 09月18日 2,409