hdu5064专题

hdu5064 Find Sequence 单调性dp

题意:给出一个数组a,之和为M,从中挑选出一些数组成数组b满足两个条件: (1)  b1≤b2≤…≤bt   (2)  b2−b1≤b3−b2≤⋯≤bt−bt−1 求最大的t。 分析:a数组排序后,由于M<=(1<<22),所以a数组数字种数不超过3000,dp[i][j]表示以i和j结尾的最长串,dp[i][j]=dp[k][i]+1,dp[i][j]具有单调性,满足dp[i][j]的