如何解决高级编码竞赛中提出的这个问题？
How to solve this question asked in premium coding contest?
有人可以指导我如何解决这个编程问题吗？好像是DP问题，我找不到答案。
问题：
There are ‘n’ ads. Each ad has an effectiveness value associated with
it which is given in an array of size ‘n’ in the format [v1, v2, …,
vn], where ‘v1’ is the effectiveness value of the first ad, ‘v2’ is
the effectiveness value of the second ad, and so on. The show in which
these ads will be shown is ‘m’ length long (starting from 0 till m),
and the time when the ads can be shown is given in the format [(a1,
b1), (a2, b2), …, (an, bn)], where ith tuple in the array denotes the
timing of the ith ad in the format (start_time, end_time). Note that
any ‘ai’ and ‘bi’ cannot be smaller than 0 and cannot be larger than
‘m’. When you choose to show an ad, you cannot show another ad within
4 minutes of it’s end. So if you select to show the ad having timings
as (2, 4), then you cannot show another ad before 9, hence next ad
cannot be (8, 10), but it can be (9, 12). You have to select the ads
to show to the audience such that you maximize the sum of the
effectiveness values of the ads, given the above constraints. For
example, if ‘m’ is 20, and the timings of the ads are [(2, 3), (6, 9),
(10, 12), (12, 13), (14, 17)] and the effectiveness values are [3, 9,
10, 6, 7], then you can show ad 2 and ad 5 (one-based-indexing) and
have an effectiveness value of 16, which is the maximum you can get
given the constraints.
您的问题可以简化为以下内容，让我们考虑可以描述为 (start_i、end_i、value_i) 的 1d 段。
令 S = 可用一维段数组
我们想要的是找到求和为最大可能值且适合区间 [0, m]（显示长度）的非相交线段
令 DP[x] = 用可用 1d 段的子集覆盖段 [0, x] 的最佳可实现值。
递归关系是，给定一个元素（s_i、e_i、v_i）我们可以select它或不它。
DP[e_i] = DP[e_i - 1]
DP[e_i] = max( DP[e_i], DP[s_i - 1] + v_i )
dp[0] = 0;
// sort the events by increasing e_i, because
// we want to process first the events that finish earlier
for( int END = 1; END <= m; ++END)
{
dp[end] = dp[end - 1];
for( each ELEMENT(s_i, e_i, v_u) with (e_i == END) )
{
dp[end] = max( dp[end], dp[s_i - 1] + v_i )
}
}
有人可以指导我如何解决这个编程问题吗？好像是DP问题，我找不到答案。
问题：
There are ‘n’ ads. Each ad has an effectiveness value associated with it which is given in an array of size ‘n’ in the format [v1, v2, …, vn], where ‘v1’ is the effectiveness value of the first ad, ‘v2’ is the effectiveness value of the second ad, and so on. The show in which these ads will be shown is ‘m’ length long (starting from 0 till m), and the time when the ads can be shown is given in the format [(a1, b1), (a2, b2), …, (an, bn)], where ith tuple in the array denotes the timing of the ith ad in the format (start_time, end_time). Note that any ‘ai’ and ‘bi’ cannot be smaller than 0 and cannot be larger than ‘m’. When you choose to show an ad, you cannot show another ad within 4 minutes of it’s end. So if you select to show the ad having timings as (2, 4), then you cannot show another ad before 9, hence next ad cannot be (8, 10), but it can be (9, 12). You have to select the ads to show to the audience such that you maximize the sum of the effectiveness values of the ads, given the above constraints. For example, if ‘m’ is 20, and the timings of the ads are [(2, 3), (6, 9), (10, 12), (12, 13), (14, 17)] and the effectiveness values are [3, 9, 10, 6, 7], then you can show ad 2 and ad 5 (one-based-indexing) and have an effectiveness value of 16, which is the maximum you can get given the constraints.
您的问题可以简化为以下内容，让我们考虑可以描述为 (start_i、end_i、value_i) 的 1d 段。
令 S = 可用一维段数组
我们想要的是找到求和为最大可能值且适合区间 [0, m]（显示长度）的非相交线段
令 DP[x] = 用可用 1d 段的子集覆盖段 [0, x] 的最佳可实现值。
递归关系是，给定一个元素（s_i、e_i、v_i）我们可以select它或不它。
DP[e_i] = DP[e_i - 1]
DP[e_i] = max( DP[e_i], DP[s_i - 1] + v_i )
dp[0] = 0;
// sort the events by increasing e_i, because
// we want to process first the events that finish earlier
for( int END = 1; END <= m; ++END)
{
dp[end] = dp[end - 1];
for( each ELEMENT(s_i, e_i, v_u) with (e_i == END) )
{
dp[end] = max( dp[end], dp[s_i - 1] + v_i )
}
}