Problems on Cycles

I have recorded quite a few problems on this blog, but my understanding of some concepts is still not strong enough, so I do not always know how to approach a new problem. This post is about problems involving cycles.

As soon as a cycle appears, it tends to be a headache. Standard dynamic programming no longer applies directly, and many things become difficult to solve.

Pizza With 3n Slices

The task reduces to this: given $n$ values in a cycle, select $n / 3$ non-adjacent values.

There was a similar problem long ago—see here. Use the same treatment: compare the maximum after removing the first element with the maximum after removing the last. The remaining part can then be treated as non-cyclic.

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));
    }
};

This can also be solved in $O(n \log n)$ with a deque and a priority queue: repeatedly pop the maximum value, then undo its effect. I think this approach is excellent.