[HNOI2008]玩具装箱toy

BZOJ1010...

这道题貌似可以用斜率优化,不过不用也行,利用决策单调性同样可以设计出O(nlogn)的算法..
 
首先可以很容易得到朴素的状态转移方程:(f(x)表示只装前x个玩具的最优解)
f(x) = min{f(k) + cost(k + 1,x)}
其中,cost(i,j)为把[i,j]这个区间内的玩具装到一个箱子里的代价:cost(i,j) = (Sj - Si + j - i - T)^2
其中,Sx = Σ(i = 1,j)Ci,Ci即为第i个箱子的长度
 
我们可以很容易发现,对于j > i,若cost(k,j) > cost(k,i),那么一定有cost(k,j + 1) > cost(k,i)(原因是cost(k,x)的函数图像开口向上且只有一个极值),而对于j > i,也有若f(j) > f(i),那么f(j + 1) > f(i)(因为f(x)是由cost(i,j)定义的)
也就是说,若f(j)的最优决策是f(i),那么f(j + 1)的最优决策也是f(i)

[ZJOI2010]count 数字计数

 
好累...我真的再也不想做数位DP了...
啊,要统计[l,r]以内0~9出现的次数,减一减然后这道题就变成了求(0,k)以内各个数位出现的次数
[1,9]都是一样的,0比较特(e)殊(xin),一会儿再说,先说怎么处理[1,9]的情况
先假设当前要处理的数位为j(1 <= j <= 9),可以DP得到f[i][j]为i位以内(即(0,10^i)以内)j出现的次数
然后就是讨论3种情况:
(设k十进制共l位,从低到高第p位为b(p))
①首位为0 (f[l - 1][j])
②首位为[1,b(l) - 1] ((b(l) - 1) * f[l - 1[j] ,若b(l) >= j则再加上10^(l - 1))
③首位为b(l),这个情况比较复杂,不过仔细思考一下还是能得出的(具体的看代码吧..)
 
然后是待求数位为0的情况,首先需要维护两个数组:f[i][0]和h[i],其中f[i][0]的含义和前面一样,h[i]表示算上前缀0,刚好i位的数中0出现次数,这两个都可以DP求(吧...)(反正我是用组合求的...)
然后还是讨论上面三种情况,公式基本不变(还是有些变动,不过都是很好推的,具体看代码吧...),但是有些地方f[i][j]要换成h[i]
 
注意有些地方区间的开闭,还有精度啊啥啥的,基本上这道题就可以A了...
 

[SCOI2009]windy数

 
写完这道题感觉心好累...这辈子都不想再做数位DP的题了,然而他们说这是道入门题...
首先可以DP得到位数为i,最高位为j的windy数个数g(i,j)
然后对于(0,k)内的windy数个数,可以讨论3种情况:(感觉数位DP就是大讨论..)
(假设总位数为l,假设k的从高到低第t位为bit(t) )
①最高位为0,位数为[1,l - 1]的windy数个数(Σ(q=1,l-1) Σ(p=1,9) g(p,q))
②最高位为[1,k - 1],位数为l的windy数个数(Σ(q=1,k-1) g(l,q))
③最高位为k的windy数个数,这个比较复杂,总之是从高位到低位依次确定,伪代码如下:
for i = (len - 1) to 1 , step -1:
  for q = 1 to bit(i) - 1 (#) , step 1: 
   if(|q - bit(i + 1)| > 2)
     sum <- sum + g(i,q)
   endif
  endfor
endfor
 
注意打#的地方,这里取bit(i) - 1是因为求的是开区间(闭区间的话会麻烦一点)
 

[CQOI2015]任务查询系统

 
啊...我的程序跑了足足15s...真是弱爆了。很好奇第一名1K+的代码量1s是怎么做到的...
总之我的作法就是对时间维护一个树状数组套权值线段树。
这里有一个树状数组的妙用,传统的树状数组是单点修改,区间询问。这里我们把它变成区间修改,单点询问,同样是利用元素的可加性:
直接把每次询问变成询问前缀,方法就是添加的时候只在左端点添加,并在右端点的后一个减去。
 
然后这样时间复杂度是O(n * log^2(m) + m * log^2(K))的...
 

啊,于是我也跟风开了个博客...

大概会写点题解扯点淡啥的吧..