自己博客上记录的题目其实也不少了，但是因为智力以及自己对一些概念的理解确实不够，导致一些题目出来还是不知道怎么想。这篇博客想说一下碰到的带环的问题。
基本上“环”这个问题一出来，就很头疼，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出最大值，然后反悔这个最大值，感觉这种做法很牛逼啊….