lightoj1017

CODE

#include <iostream>
#include <algorithm>
#include <cstring>
int nCase;
using namespace std;
int n,w,k;
int y[105],tp;
int dp[105][105];
int main()
{
        int t;
        cin >> t;
        while(t--)
        {
                memset(dp,0,sizeof(dp));
                cin >> n >> w >> k;
                for(int i=0;i<n;i++)
                        cin >> tp >> y[i];
                sort(y,y+n);
                for(int i=1;i<=n;i++)
                        for(int j=1;j<=k;j++)
                {
                        int l,res=0;
                        for(l=0;i-l-1>=0;l++)
                        {
                                if(y[i-1]-y[i-l-1]>w)break;
                                res++;
                        }
                        dp[i][j]=max(dp[i-1][j],dp[i-l][j-1]+res);
                }
                cout << "Case "<<++nCase<<": "<<dp[n][k]<<endl;
        }
        return 0;
}