1 条题解

  • 0
    @ 2025-4-10 15:40:31
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 50;
    // 避免 INF+INF 溢出
    const int INF = 2147483647 / 2;
    int n, c;
    int pos[MAXN + 5], w[MAXN + 5];
    int sum[MAXN + 5]; // 功率前缀和
    // 把 l~r 的灯关完,最后停在 左0/右1 时的最小耗电
    int dp[MAXN + 5][MAXN + 5][2];
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n >> c;
        for (int i = 1; i <= n; i++)
        {
            cin >> pos[i] >> w[i];
            sum[i] = sum[i - 1] + w[i];
        }
    
        for (int i = 1; i <= n; i++)
            dp[i][i][0] = dp[i][i][1] = INF;
        dp[c][c][0] = dp[c][c][1] = 0;
        for (int len = 2; len <= n; len++)
        {
            for (int l = 1; l + len - 1 <= n; l++)
            {
                int r = l + len - 1;
                int now; // 当前所有开着的灯的功率之和
                // 计算 dp[l][r][0]
                // 先把 l+1 ~ r 都关掉,然后走到 l
                // 最后走到 l 时,除了 l+1~r 之外都开着
                now = sum[n] - (sum[r] - sum[(l + 1) - 1]);
                dp[l][r][0] = min((pos[l + 1] - pos[l]) * now + dp[l + 1][r][0],
                                  (pos[r] - pos[l]) * now + dp[l + 1][r][1]);
                // 计算 dp[l][r][1]
                // 先把 l ~ r-1 都关掉,然后走到 r
                // 最后走到 r 时,除了 l~r-1 之外都开着
                now = sum[n] - (sum[r - 1] - sum[l - 1]);
                dp[l][r][1] = min((pos[r] - pos[r - 1]) * now + dp[l][r - 1][1],
                                  (pos[r] - pos[l]) * now + dp[l][r - 1][0]);
            }
        }
        cout << min(dp[1][n][0], dp[1][n][1]);
        return 0;
    }
    
    • 1

    信息

    ID
    13392
    时间
    1000ms
    内存
    512MiB
    难度
    8
    标签
    递交数
    11
    已通过
    8
    上传者