【USACO 2011 March Gold】切蛋糕c++ AC代码

【USACO 2011 March Gold】题目“Cutting Cake”是一个经典的动态规划问题，涉及到贪心算法和区间划分策略。在这个问题中，你需要确定如何切割一块蛋糕，使得最多能得到的人数最大。每个请求都是一个人想要的一块蛋糕的起始和结束位置。

以下是一个简单的C++解决方案概述：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, queries;
    cin >> n >> queries;
    vector<int> cake(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> cake[i];
    }

    // 初始化dp数组，dp[i]表示从1到i区间的最大人数
    vector<int> dp(n + 1, 1);  // 假设每个人只能分得一块蛋糕，即初始状态下最多1人
    for (int q = 1; q <= queries; q++) {
        int start, end;
        cin >> start >> end;
        // 更新dp值，考虑将蛋糕切割在start和end之间
        if (start > 1) {
            dp[end] = max(dp[end], dp[start - 1] + 1);  // 如果之前有人能分到蛋糕，则加一
        }
        // 检查切割后是否可以给更多人
        for (int i = start; i <= n && i <= end; i++) {
            dp[i] = max(dp[i], dp[i - 1] + 1);
        }
    }

    // 输出最大人数
    cout << dp[n] << endl;

    return 0;
}

关键在于理解每个分割点对后续区间人数的影响，并更新动态规划数组。注意边界条件，比如当开始位置大于1时，前一个人可能已经获得了蛋糕，所以当前人的最大人数会增加。