题意分析

题目描述Jimmy在环形道路上投递包裹的场景。环形道路上有N个点（包括起点），起点位置为0，其他N-1个点需要投递包裹。移动规则如下：

• Jimmy从起点（0点）出发，可选择顺时针或逆时针方向移动
• 每移动一个路段需要固定时间（输入中给出相邻点顺时针移动时间）
• 每个投递点有特定数量的包裹，投递不耗时
• 罚金计算：从24:00开始，每延迟一分钟，每个未投递包裹罚1美元
• 目标：找到一条路径，使总罚金最小（总罚金 = Σ(每个包裹的投递时间 × 该点包裹数)

输入格式：

• 首行整数N（总点数，包含起点）
• 后续N行：每行两个整数m（包裹数）和t（顺时针到下一站时间）
  • 起点m=0，其他点m>0
  • 最后一点t表示返回起点时间

输出：最小罚金整数

关键约束：

• 环形路径，可任意选择方向
• 投递不耗时，移动耗时影响罚金
• 包裹投递后停止计罚金
• N ≤ 300，罚金 < 1e9

解题思路

1. 问题建模

• 环形转线性：添加虚拟终点（起点副本），形成线性序列（0,1,...,N-1,0'），便于DP处理
• 时间预处理：
  • clock_time[i]：从起点0顺时针到点i的时间（前缀和）
  • anti_clock_time[i]：从点i顺时针到虚拟终点的时间（后缀和）
• 包裹前缀和：w[i][j]表示点i到j的包裹总数，用于计算移动时的罚金

2. 动态规划定义

• 状态设计：
  • l[i][j]：投递区间[i,j]的所有点后，最后停在左端点i的最小罚金
  • r[i][j]：投递区间[i,j]的所有点后，最后停在右端点j的最小罚金
• 状态转移：
  • 向左扩展（从i+1移动到i）：
    • 移动耗时：timen[i]（i→i+1的顺时针时间）
    • 影响包裹：区间[i+1,j]的包裹数w[i+1][j]
    • 转移方程：
      l[i][j] = min(l[i+1][j] + timen[i] * w[i+1][j], ...)
  • 向右扩展（从j-1移动到j）：
    • 移动耗时：timen[j-1]（j-1→j的顺时针时间）
    • 影响包裹：区间[i,j-1]的包裹数w[i][j-1]
    • 转移方程：
      r[i][j] = min(r[i][j-1] + timen[j-1] * w[i][j-1], ...)
  • 跨环跳跃（通过虚拟终点）：
    • 移动耗时：clock_time[i] + anti_clock_time[j]（从j→0'→i）
    • 转移方程：
      l[i][j] = min(..., r[i+1][j] + (clock_time[i] + anti_clock_time[j]) * w[i+1][j])
r[i][j] = min(..., l[i][j-1] + (clock_time[i] + anti_clock_time[j]) * w[i][j-1])

3. 算法流程

1. 初始化：
   • 读入N，扩展为N+1（添加虚拟终点）
   • 计算时间前缀/后缀和
   • 初始化单点区间l[i][i] = r[i][i] = 0
2. 区间DP枚举：
   • 枚举区间长度k从1到N
   • 枚举左端点i，计算右端点j = i+k
   • 按转移方程更新l[i][j]和r[i][j]
3. 输出结果：
   min(l[0][N], r[0][N])（虚拟终点对应索引N）

4. 复杂度分析

• 时间复杂度：O(N²)（两重循环）
• 空间复杂度：O(N²)（存储DP表）

代码实现（C++）

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 310;
const int INF = 1000000000;

int timen[MAXN], num[MAXN];
int clock_time[MAXN], anti_clock_time[MAXN];
int w[MAXN][MAXN], l[MAXN][MAXN], r[MAXN][MAXN];

int main() {
    int n;
    while (cin >> n && n != 0) {
        // 读入数据
        for (int i = 0; i < n; i++) 
            cin >> num[i] >> timen[i];
        
        // 环形转线性：添加虚拟终点（起点副本）
        num[n] = 0;
        timen[n] = 0;
        n++;
        
        // 预处理时间
        clock_time[0] = 0;
        for (int i = 1; i < n; i++) 
            clock_time[i] = clock_time[i-1] + timen[i-1];
        
        anti_clock_time[n-1] = 0;
        for (int i = n-2; i >= 0; i--) 
            anti_clock_time[i] = anti_clock_time[i+1] + timen[i];
        
        // 预处理包裹前缀和
        for (int i = 0; i < n; i++) {
            w[i][i] = num[i];
            for (int j = i+1; j < n; j++)
                w[i][j] = w[i][j-1] + num[j];
        }
        
        // 初始化DP表
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) l[i][j] = r[i][j] = 0;
                else l[i][j] = r[i][j] = INF;
            }
        }
        
        // 区间DP
        for (int len = 1; len < n; len++) {
            for (int i = 0; i + len < n; i++) {
                int j = i + len;
                // 更新l[i][j]：最后停在左端点
                l[i][j] = min(
                    l[i+1][j] + timen[i] * w[i+1][j], 
                    r[i+1][j] + (clock_time[i] + anti_clock_time[j]) * w[i+1][j]
                );
                // 更新r[i][j]：最后停在右端点
                r[i][j] = min(
                    r[i][j-1] + timen[j-1] * w[i][j-1], 
                    l[i][j-1] + (clock_time[i] + anti_clock_time[j]) * w[i][j-1]
                );
            }
        }
        
        // 输出最小罚金
        cout << min(l[0][n-1], r[0][n-1]) << endl;
    }
    return 0;
}

示例解析

输入样例1：

4
0 1
6 10
9 50
5 5

处理流程：

1. 扩展为5个点：添加虚拟终点(0,0)
2. 时间预处理：
   • clock_time = [0,1,11,61,66]
   • anti_clock_time = [66,65,55,5,0]
3. 关键DP转移：
   • 小区间优先计算（如[1,2]）
   • 大区间依赖小区间结果（如[0,4]）
4. 输出：min(l[0][4], r[0][4]) = 240