如何解决高级编码竞赛中提出的这个问题? [英] How to solve this question asked in premium coding contest?

问题描述

有人可以指导我如何解决这个编程问题吗?好像是DP问题，我找不到答案.

Could someone guide me on how to solve this programming question? It seems something like DP problem which I couldn't find answer for.

问题:

有"n"个广告.每个广告都有一个与 它以大小为'n'的数组给出，格式为[v1，v2，…， vn]，其中"v1"是第一个广告的效果值，"v2"是 第二个广告的有效性值，依此类推.该节目在其中 这些广告的长度为"m"(从0到m)， 并且可以展示广告的时间以[[a1， b1)，(a2，b2)，…，(an，bn)]，其中数组中的第一个元组表示 第i个广告的时间格式(开始时间，结束时间).注意 任何"ai"和"bi"都不能小于0且不能大于 ‘m’.选择展示广告时，您不能在其中展示其他广告 结束了4分钟因此，如果您选择显示带有时间的广告 如(2，4)，则您不能在9之前显示另一个广告，因此下一个广告 不能为(8，10)，但可以为(9，12).您必须选择广告 向观众展示，使您最大程度地增加 在上述限制条件下，广告的有效性值.为了 例如，如果"m"为20，并且广告的时间为[(2，3)，(6，9)， (10，12)，(12，13)，(14，17)]，有效值为[3，9， 10、6、7]，则您可以展示广告2和广告5(基于索引的索引)， 有效性值为16，这是您可以获得的最大值 给定约束.

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段.

Your problem can be reduced to the following, let's consider 1d segments that can be described as (start_i, end_i, value_i).

让S =可用的一维线段的数组

Let S = array of available 1d segments

我们想要的是找到不相交的线段，这些线段的总和为最大可能值，并适合在[0，m](显示长度)区间内

What we want is to find the non-intersecting segments that sum to the maximum possible value and fit in the interval [0, m] ( show length )

让DP [x] =可用段1d段的子集覆盖段[0，x]的最佳可实现值.

Let DP[x] = best achievable value to cover the segment [0, x] with a subset of the available 1d segments.

递归关系是，给定一个元素(s_i，e_i，v_i)，我们可以选择或不选择它.

The recurrence relation is, given an element (s_i, e_i, v_i) we can select it or not.

DP [e_i] = DP [e_i-1]

DP[e_i] = DP[e_i - 1]

DP [e_i] = max(DP [e_i]，DP [s_i-1] + v_i)

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 ) 
    }
}

这篇关于如何解决高级编码竞赛中提出的这个问题?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！