环路问题

自己博客上记录的题目其实也不少了,但是因为智力以及自己对一些概念的理解确实不够,导致一些题目出来还是不知道怎么想。这篇博客想说一下碰到的带环的问题。

基本上“环”这个问题一出来,就很头疼,dp也没办法dp,然后很多东西很难去解。

Pizza With 3n Slices

题意最后化成了,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出最大值,然后反悔这个最大值,感觉这种做法很牛逼啊….