LightOJ 1017 - Brush (III)【一般DP】

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/49016009

题目链接： http://www.lightoj.com/volume_showproblem.php?problem=1017

题意：
给你一把刷子，每次最多刷w宽的区域，给你n个点的间距，最多刷k次，问你最多能刷到几个点。

解法：
按坐标排序。
dp[i][j] 表示刷到i用j次最优解，用num[i]记录i位置最多能刷多少个。

代码：

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <sstream>

using namespace std;

int n, w, k;
int dp[110][110];

struct Node
{
    int x;
    int y;
}a[100010];

bool cmp(Node a, Node b)
{
    return a.y < b.y;
}

int num[110];

int main()
{
    int t, cases = 1;
    scanf("%d", &t);
    while (t--)
    {
        memset(num, 0, sizeof(num));
        scanf("%d%d%d", &n, &w, &k);
        for (int i = 1;i <= n;i++)
            scanf("%d%d", &a[i].x, &a[i].y);
        sort(a + 1, a + 1 + n, cmp);

        for (int i = 1;i <= n;i++)
        {
            int tmp = 0;
            for (int j = 1;j <= i;j++)
            {
                if ((long long)(a[i].y - a[j].y) <= w)
                    tmp++;
            }
            num[i] = tmp;
        }
        memset(dp, 0, sizeof(dp));

        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= k;j++)
            {
                dp[i][j] = 1;
                if (i < num[i])
                    dp[i][j] = num[i];
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i-num[i]][j-1] + num[i]);
            }
        printf("Case %d: %d\n", cases++, dp[n][k]);
    }
    return 0;
}