LightOJ 1017 Brush (III) (DP)

曾经终败给现在 2022-09-18 04:59 118阅读 0赞

题目链接：http://lightoj.com/volume\_showproblem.php?problem=1017

题意：坐标系里有n个点，一个宽度为w的刷子可以擦去这些点(边缘擦到也算)，刷子可以横向无限移动，问移动k次最多可以擦去多少点。

思路：显然与点的横坐标无关，将纵坐标排序，预处理：以刷子的底边擦去一个点i会向上影响多少个点mv\[i\]。

状态转移方程：dp\[i\]\[j\]=max(dp\[i-1\]\[j\],dp\[i-mv\[i\]\]\[j-1\]+mv\[i\]),前一项表示不删点i，后一项表示把它和它会影响的点都删掉。

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    #define max(a,b) ((a)>(b)?(a):(b))
    
    const int N=101;
    
    int y[N],mv[N];
    int dp[N][N];
    
    bool cmp (int a,int b)
    {
    	return a>=b;
    }
    
    int main ()
    {  
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		int n,w,k,i;
    		scanf("%d%d%d",&n,&w,&k);
    		for (i=0;i<n;i++)
    			scanf("%*d%d",&y[i]);
    		memset(dp,0,sizeof(dp));
    		memset(mv,0,sizeof(mv));
    		sort(y,y+n,cmp);   //降序
    		for (i=0;i<n;i++)  //预处理
    		{
    			int high=i,low=i;
    			while (y[high]-y[low]<=w && high>=0)
    				high--;
    			mv[i]=low-high; //以i为底边,最高会影响多少个点
    		}
    		for (i=0;i<n;i++) for (int j=1;j<=k;j++)
    			if (i>=mv[i])   //
    				dp[i][j]=max(dp[i-1][j],dp[i-mv[i]][j-1]+mv[i]);//不擦i,擦i
    			else //else if (i==mv[i]-1)也可,此时说明擦去此点会同时擦掉它和之上的所有点
    				dp[i][j]=mv[i];
    		printf("Case %d: %d\n",Cas,dp[n-1][k]);
    	}
    	return 0;
    }
    
    /*
    In:
    6
     
    3 2 1
    0 0
    20 2
    30 2
     
    3 1 1
    0 0
    20 2
    30 2
    
    5 3 1
    0 0
    0 3
    0 4
    0 5
    0 6
    
    7 15 2
    0 4
    0 6
    0 12
    0 27
    0 38
    0 46
    0 50
    
    10 16 3
    0 9
    0 19
    0 21
    0 29
    0 44
    0 57
    0 72
    0 83
    0 94
    0 97
    
    10 10 2
    0 7
    0 11
    0 14
    0 18
    0 27
    0 34
    0 37
    0 38
    0 43
    0 50
    
    Out
    Case 1: 3
    Case 2: 2
    Case 3: 4
    Case 4: 6
    Case 5: 8
    Case 6: 7
    */