LightOJ1017 Brush (III)（DP）

题目大概说一个平面上分布n个灰尘，现在要用一个宽w的刷子清理灰尘：选择一个起点，往水平线上扫过去这个水平线上的灰尘就消失了。问最多进行k次这样的操作能清理最多多少灰尘。

没什么的DP。

• 先按垂直坐标给灰尘们排个序，
• 然后d[i][k]表示前i个灰尘中，进行到第k次清理操作时刷子底部在第i个灰尘的竖坐标能清理的最多灰尘，
• 最后转移一个一个往前枚举就OK了，规模很小。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int d[][];

 int main(){

     int t,n,w,K,x[],y;

     scanf("%d",&t);

     for(int cse=; cse<=t; ++cse){

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

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

             scanf("%d%d",&y,x+i);

         }

         sort(x,x+n);

         memset(d,,sizeof(d));

         d[][]=;

         int res=;

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

             int cnt=;

             for(int k=; k<i; ++k){

                 if(x[i]-x[k]<=w){

                     ++cnt;

                 }

             }

             d[i][]=cnt;

             res=max(res,d[i][]);

             for(int j=; j<=K; ++j){

                 int mx=;

                 for(int k=; k<i; ++k){

                     if(x[i]-x[k]<=w){

                         break;

                     }

                     mx=max(mx,d[k][j-]);

                 }

                 if(mx!=){

                     d[i][j]=mx+d[i][];

                     res=max(res,d[i][j]);

                 }

             }

         }

         printf("Case %d: %d\n",cse,res);

     }

     return ;

 }