lightoj 1017

思路：动态规划，设dp[i][j]表示在前j个dusts中用了i刷子刷掉dusts的个数：状态转移方程就是： dp[i][j] = max(dp[i][j-1], dp[i-1][j-len[j]] + len[j]);    len[j]表示刷第j个dust时需要覆盖其前面dusts的个数，可以在O(n)或O(n^2)的时间复杂度内预处理出来。

#include<cstdio>

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int MAXN = 101;

int dp[MAXN][MAXN], len[MAXN], y[MAXN];

int main(){

    int t, w, K, n, x, CASE(0);

    scanf("%d", &t);

    while(t--){

        scanf("%d%d%d", &n, &w, &K);

        for(int i = 0;i < n;i ++) scanf("%d%d", &x, y+i);

        sort(y, y+n);

        memset(len, 0, sizeof len);

        for(int i = 0;i < n;i ++){

            for(int j = i;y[i]-y[j] <= w && j >= 0;j --) len[i+1]++;

        }

        memset(dp, 0, sizeof dp);

        for(int i = 1;i <= K;i ++){

            for(int j = 1;j <= n;j ++){

                dp[i][j] = max(dp[i][j-1], dp[i-1][j-len[j]] + len[j]);

            }

        }

        printf("Case %d: %d\n", ++CASE, dp[K][n]);

    }

    return 0;

}