cf544E

转移自老blog

cf544E

链接

题意

        给你n个数,分成k组,允许某些数不放,要求每组内最大值与最小值的差值不超过5。求k组最多可以放多少个数。

题解

        排序后预处理每个数向左延伸的最远位置,l[i]
        设:
        dp[i][j] 前i个数分j组最多能放多少个数 
        dp[i][j]=max(dp[i−1][j],dp[i][j−1],dp[l[i]−1][j−1]+i−l[i]+1)