E. Antenna Coverage

发表于 | 阅读数

E

E

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int dp[N], x[N], s[N], n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &x[i], &s[i]);
    dp[0] = 0;
    for (int i = 1; i <= m; i++)
        dp[i] = i;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (x[j] >= i)
                dp[i] = min(dp[i], dp[max(x[j] - s[j] - 1, 0)]);
            else
                dp[i] = min(dp[i], dp[max(min(2 * x[j] - i - 1, x[j] - s[j] - 1), 0)] + max(0, i - (x[j] + s[j])));
        }
    }
    printf("%d\n", dp[m]);
}