Educational Codeforces Round 59 (Rated for Div. 2)

發表於 更新於 分類於 ， Disqus： 文章字數： 327 所需閱讀時間 ≈ 1 分鐘
E 看似n方，实则O(n)的三分dp

题目HERE

题目大意给

01串 长度<=100

每次可以任选一段连续的相同数字的串删掉，删掉的代价为cost[长度]，删掉后 原来的串两端相连，求这样操作直到删空，cost和的最大值

如 0011100 删掉中间连续3个1 变成0000，并且获得cost[3]

样例

1
2
3
7
1101001
3 4 9 100 1 2 3

输出109

1101001 → 111001 → 11101 → 1111 → ∅.

解法

状态 dp[开始index][结束index(不包括)][?->开始index 相同的数字的长度len]

[开始index,结束index)且开始的左边还有 len-1个和s[开始index]相同的数字

状态转移

dp[start][end][len] = max(A[len]+dp[start+1][end][1],max(dp[start+1][itr][1]+dp[itr][end][len+1])), 其中s[itr] == s[start]

举例解释

1
2
3
4
5
6
11111100001111011
yyyy
   s             e
          i
   4=len
    xxxxxx

上面假设在求 dp[s][e][len]

那么A[len]+dp[s+1][end][1]表示先一次处理掉yyyy对应部分 再处理s以后的部分

那么dp[s+1][i][1]表示把xxxxx对应部分处理掉的代价,dp[i][e][len+1]表示的是 处理掉xxxxx这部分后，在处理剩余部分的代价

所以最终，答案就是dp[0][N][1]

状态O(n^3)状态转移O(N)所以总时间复杂度 O(N^4)

code