题目描述：
给你一个披萨，它由 $3n$ 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：
- 你挑选任意一块披萨。
- Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
- Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
- 重复上述过程直到没有披萨剩下。
每一块披萨的大小按顺时针方向由循环数组 slices 表示。
请你返回你可以获得的披萨大小总和的最大值。
数据范围：
$1\le slices.len \le 500; slices.len \mod 3 = 0;1\le slices.len \le 1000$
题解：
动态规划：
可以将问题转化为在一个长度为 $3n$ 的环形数组中，选择 $n$ 个不相邻的数，使得这 $n$ 个数的和最大。
由于环形数组中，如果选择了第一个数，那么就不能选择最后一个数，因此可以将数组拆分成两个数组，一个是去掉第一个数的（表示不选第一个数）；另一个是去掉最后一个数的（表示不选最后一个数）。分别求两个数组的最大值，然后取较大的即可。
使用 $dp[i][j]$ 表示在数组的前 $i$ 个数中取 $j$ 个不相邻数的最大值。那么对于 $nums[i]$ 来说，如果取，则 $dp[i][j] = dp[i-2][j-1] + nums[i]$ ；如果不取则 $dp[i][j] = dp[i-1][j]$ 。可以得到状态转移方程（下标从 $1$ 开始）：
复杂度是 $O(N^2)$
优先级队列：
使用优先级队列加回溯技巧。
按照贪心的思路，每次肯定是取最大值，但是这样可能得不到最优解，可能取了一些最大值旁边的是最优解。
如1 1 6 8 9 8：贪心得到 9 + 6 = 15
但是最优解是 8 + 8 = 16
使用一种回溯机制，取当前点后，弹出优先级队列，然后把 $left + right - cur$ 加入队列。
这样的话就可以解决上述问题。
假设继续按照贪心，第一次取出了 $9$ ，加入 8 + 8 - 9 = 7，接下来取出 8 8跳过，然后取出了 $7$ ，得到 $9 + 7 = 16$ 。即是 9 + 8 + 8 - 9，实际上取出的是 8 8。
使用双向链表维护，这样可以快速查找左侧和右侧的值。
代码：
动态规划
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
30
31
32
33
34
35
36
37
38
39
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int solve(vector<int> &slices)
{
int N = slices.size();
int n = (N + 1) / 3;
vector<vector<int>> dp(N + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= N; ++i)
{
for (int j = 1; j <= n; ++j)
{
if (i >= 2)
dp[i][j] = max(dp[i - 1][j], dp[i - 2][j - 1] + slices[i - 1]);
else
dp[i][j] = max(dp[i - 1][j], slices[i - 1]);
}
}
return dp[N][n];
}
int maxSizeSlices(vector<int> &slices)
{
vector<int> s(slices.begin(), slices.end() - 1);
int ans1 = solve(s);
s = vector<int>(slices.begin() + 1, slices.end());
int ans2 = solve(s);
return max(ans1, ans2);
}
};
|
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
struct Node
{
int val;
int id;
int l, r;
bool vis;
bool operator<(const Node &p) const
{
return val < p.val;
}
};
vector<Node> l;
priority_queue<Node> q;
void remove(Node &node)
{
l[node.id].vis = true;
l[node.l].r = node.r;
l[node.r].l = node.l;
}
int maxSizeSlices(vector<int> &slices)
{
int N = slices.size();
int n = (N + 1) / 3;
l.resize(N);
for (int i = 0; i < N; ++i)
{
l[i].id = i;
l[i].l = (i - 1 + N) % N;
l[i].r = (i + 1) % N;
l[i].val = slices[i];
l[i].vis = false;
q.push(l[i]);
}
int ans = 0;
int cnt = 0;
while (cnt < n)
{
auto out = q.top();
q.pop();
if (l[out.id].vis)
continue;
ans += l[out.id].val;
cnt++;
int left = l[out.id].l;
int right = l[out.id].r;
l[out.id].val = l[left].val + l[right].val - l[out.id].val;
remove(l[left]);
remove(l[right]);
q.push(l[out.id]);
}
return ans;
}
};
|