自己博客上记录的题目其实也不少了,但是因为智力以及自己对一些概念的理解确实不够,导致一些题目出来还是不知道怎么想。这篇博客想说一下碰到的带环的问题。
基本上“环”这个问题一出来,就很头疼,dp也没办法dp,然后很多东西很难去解。
题意最后化成了,n个数,环形,如果要取非相邻的n/3个,怎么搞。
其实这个题很早以前就有过类似的,见这里,一样的处理方法。比较去掉第一个 或者 最后一个,这两种情况下的最大值。剩余部分就当作没有环来处理了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| class Solution { public: int dp[505][505]; int val[505]; int cal(std::vector<int> v) { memset(dp, 0, sizeof(dp)); for(int i=0;i<v.size(); i++) { val[i+1] = v[i]; DE(val[i+1]) } int n = (v.size()+1) / 3; int m = v.size(); int ans = 0; for(int i = 1; i <= n; i++) { int pre_max = 0; for(int j = 1; j <= m; j++) { if(j>=2) pre_max = max(pre_max, dp[i-1][j-2]); dp[i][j] = max(dp[i][j], pre_max + val[j]); ans = max(ans, dp[i][j]); } } return ans; } int maxSizeSlices(vector<int>& slices) { vector<int> v1(slices.begin() + 1 , slices.end()); vector<int> v2(slices.begin(), prev(slices.end())); return max(cal(v1), cal(v2)); } };
|
当然这个题还可以O(nlogn)来搞,双端队列 + 优先队列,每次都pop出最大值,然后反悔这个最大值,感觉这种做法很牛逼啊….