先算出各个数字出现的次数
不妨假设最后一位是0(是5的情况同样处理)
去掉这个0后,求用剩下的数字组成模3余0的最大数,实际上就是求一个组合,
使得所有数的和模3余0,组合里的数越多越好,大的数越多越好.
设f[i][j]表示只取0,1,...,i中的数且和模3余j的最优选法(就是选得最多)
显然f[0][0] = count[0], f[0][1] = -INF, f[0][2] = -INF;
f[i][j] = Max{f[i-1][(j-k*i)%3] + k}, k = 0,1,...,count[i]
f[9][0]是除去最后一位后的最大长度.
求出了f[][],就可以倒推出9最多多少个,8最多多少个
然后按从大到小输出,跟上一个0
末位是5的情况同上,求f[9][1]即可

• 刚过的，WA的不行了，觉得排序以后DP比较好吧． (381) nuanran 2006-08-14 23:34:49
  • 我想是dp[i][j][k]，0<i<n(第i位），0<j<3(余数为j），k=0,1(表示最后一个选不选），有点像2889那道题 (0) xiaolonghingis 2006-08-14 23:42:06