URAL 2052 Physical Education(数位dp)

作者:武汉味美食家餐饮管理有限公司 来源:www.cj17917.com 发布时间:2017-09-11 14:22:07
URAL 2052 Physical Education(数位dp)

题意:给出一个自然数数列,按照每个数的所有数位之和作为第一关键字,每个数的大小作为第二关键字升序排序,位置不变的数的个数是多少。

思路:首先可以证明,对于数位和为i的所有数,最多只可能有一个位置不变,这个可以直观的猜想一下,因为如果有一个数字位置不变,那么对于排序后的序列,这个数后面的所有数的增长速度都大于自然数序列的增长速度,所以不可能再有第二个。

假设我们当前求出了数位和为i的区间为[l, r],令query(a, b)表示1到a这段区间内数位和为b的数的个数,用su[i-1]表示数位和为1到i-1的数的个数。

那么对于区间[l, l+query(l-1, i) -1],一定不存在位置不变的数,因为这些数都小于l,

那么我们就把区间缩小为了[su[i-1]+query(l-1, i)+1, su[i-1]+query(r, i)],因为至多只存在一个位置不变的数,所以这个区间肯定可以一直缩小下去,这个递归来做就可以。

递归的出口是l==r且su[i-1]+query(l-1, i)+1==su[i-1]+query(r,i),这时返回1,否则返回0。也就是说,这时l位置的这个数就是位置不变的一个数。

现在问题转化为了求query,对于这个问题,我们用一个辅助的数组dp[][][]帮助我们计算,dp[i][j][k]表示一个第i位为j数字和为k的数有多少,并且第i位是这个数的最高位。

对于query,每次如果当前位的数字比给定的n的这一位的数字小,那么后面可以随便选,这样一来就可以解决query的问题,具体见代码。

#include #include #include #include #include #include #include #include

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:武汉网站设计 http://www.45qun.com

  • 上一篇:Python实现抓取CSDN首页文章列表
  • 下一篇:最后一页
  • 
    COPYRIGHT © 2015 武汉味美食家餐饮管理有限公司 ALL RIGHTS RESERVED.
    本站所有原创信息,未经许可请勿任意转载或复制使用 网站地图 技术支持:肥猫科技
    精彩专题:网站建设
    购买本站友情链接、项目合作请联系客服QQ:2500-38-100