鸿 网 互 联 www.68idc.cn

当前位置 : 主页 > 编程语言开发 > c++ > >

Brush (III) LightOJ - 1017

来源:互联网 作者:佚名 时间:2018-02-06 18:04
Brush (III) LightOJ - 1017 题意:有一些点,每刷一次可以将纵坐标在区间(y1,y1+w)范围内的所有点刷光,y1为任何实数。最多能刷k次,求最多共能刷掉几个点。 先将点按照纵坐标从小到大排序。 显然,横坐标没有任何作用。记p[i]为排序后第i个点的纵坐标。 显

Brush (III) LightOJ - 1017

题意:有一些点,每刷一次可以将纵坐标在区间(y1,y1+w)范围内的所有点刷光,y1为任何实数。最多能刷k次,求最多共能刷掉几个点。

先将点按照纵坐标从小到大排序。

显然,横坐标没有任何作用。记p[i]为排序后第i个点的纵坐标。

显然,每一次以某个点的纵坐标为y1来刷,一定不会比以其他的数为y1来刷更差。

记x[i]为以第i个的纵坐标为y1来刷能刷掉的点的数量。容易预处理出来。

ans[i][j]表示以第i个的纵坐标为y1,刷j次能刷掉的点数量的最大值。那么ans[i][1]首先就可以有一个值为x[i]。其次,ans[i][j]也可以由之前的状态(ans[j1][j-1])转移过来。由于如果p[j1]+w>=p[i],那么会导致清除的点有重复,因此只有p[j1]+w<p[i]时才能转移。转移时的操作就是$ans[i][j]=max(ans[i][j],ans[j1][j-1]+x[i])$。

最后答案就是所有ans[i][j]中最大值。

修改记录:

1.原先做了离散化,后来发现没用,就去掉了

2.原先在36和37行之间多了几行

for(j=1;j<=k;j++)
    for(j1=1;j1<i;j1++)
        ans[i][j]=max(ans[i][j],ans[j1][j]);

发现没用,就去掉了。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int p[110],x[110],ans[110][110];
 6 int T,TT,n,w,k,maxans;
 7 int main()
 8 {
 9     int i,j,j1,t;
10     scanf("%d",&T);
11     for(TT=1;TT<=T;TT++)
12     {
13         scanf("%d%d%d",&n,&w,&k);
14         for(i=1;i<=n;i++)
15             scanf("%d%d",&t,&p[i]);
16         sort(p+1,p+n+1);
17         maxans=0;
18         memset(ans,0,sizeof(ans));
19         memset(x,0,sizeof(x));
20         for(i=1;i<=n;i++)
21             for(j=i;j<=n;j++)
22             {
23                 if(p[j]-p[i]>w)    break;
24                 x[i]++;
25             }
26         for(i=1;i<=n;i++)
27         {
28             ans[i][1]=x[i];
29             maxans=max(maxans,ans[i][1]);
30             for(j=1;j<=k;j++)
31                 for(j1=1;j1<i;j1++)
32                 {
33                     if(p[i]-p[j1]<=w)    break;
34                     ans[i][j]=max(ans[i][j],ans[j1][j-1]+x[i]);
35                     maxans=max(maxans,ans[i][j]);
36                 }
37         }
38         printf("Case %d: %d\n",TT,maxans);
39     }
40     return 0;
41 }
网友评论
<