首页 > 代码库 > lightoj1017_dp

lightoj1017_dp

2024-08-15 17:59:23   220人阅读

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

题目大意：
    在一个二维平面上有N个点，散落在这个平面上。现在要清理这些点。有一个刷子刷子的宽度是w. 刷子上连着一根绳子，刷子可以水平的移动（在X轴方向上）。他可以把刷子放在任何一个地方然后开始移动(只能是水平的)。 他可以把在宽度为w的这个水平方向上的所有点都擦除掉。问最多移动k次，最多可以擦除多少个点？
题目解析：
    根据题意，其实我们只需要考虑y坐标就OK了。 然后排序，把数据处理一下。
    dp[i][k] = dp[第i个位置][移动的是第k次] = 最大数量
    我们把数据预处理一下。 把每个位置以这个为起点，最大能包住多少个点。
技术分享
 1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <vector> 7 #include <ctime> 8 #include <queue> 9 #include <list>10 #include <set>11 #include <map>12 using namespace std;13 #define INF 0x3f3f3f3f14 typedef long long LL;15 16 int x[110], a[110];17 int dp[110][110];18 int main()19 {20     int t, n, w, k;21     scanf("%d", &t);22     for(int ca = 1; ca <= t; ca++)23     {24         scanf("%d %d %d", &n, &w, &k);25         for(int i = 0; i < n; i++)26             scanf("%d %d", &x[i], &a[i]);27         sort(a, a+n);28         memset(dp, 0, sizeof(dp));29         int res = 0;30         for(int i = 0; i < n; i++)31         {32             for(int j = i; j < n; j++)33             {34                 if(a[j] - a[i] <= w)35                     dp[i][1]++;36                 else37                     break;38             }39             res = max(res, dp[i][1]);40         }41         for(int i = 1; i < n; i++)42         {43             for(int j = 2; j <= k; j++)44             {45                 for(int l = 0; l < i; l++)46                 {47                     if(a[i] - a[l] > w)48                         dp[i][j] = max(dp[i][j], dp[l][j-1] + dp[i][1]);49                     else50                         break;                    51                 }52                 res = max(res, dp[i][j]);53             }54         }55         printf("Case %d: %d\n", ca, res);56     }57     return 0;58 }
View Code

 

lightoj1017_dp


联系
我们