W Intervals 太巧妙了

[qodjf]

dp[i] = max(sum[i] + dp[j] - common_sum(i, j))
= sum[i] + max(dp[j] - common_sum(i,j))

进入一个区间时 -a，离开一个区间时 +a。当走到 i 位置时，所有还没有关闭的区间 j 都会受到一个惩罚。所以在任意时刻，dp 数组维护的是 dp[j] - common_sum(i,j)。当走过最后一个区间时，由于对于任意 j，common_sum(i, j) 等于 0，所以 max(dp) 就是答案。

[SamZhangQingChuan]

嗯都可以啦