NOIP集训-10.31总结
NOIP集训-11.3总结

NOIP集训-11.02总结

YYY posted @ 2015年11月02日 16:33 in OI相关 with tags 对数 DP 割边 , 486 阅读
_THIS_IS_START_OF_ARTICLE_
好难...果断挂零..
----------------------------------------------------------------------
 
Ball:SuperOjP990
因为要乘起来比大小,两边取对数,每一项取一下log加起来比一比就好
好像有一些奇怪的不用log的算法...
----------------------------------------------------------------------
Array:SuperOjP991
首先把每一项都减一,这样费用cost(a,b)就变成了(sum(b)-sum(a-1)),sum(i)表示前i个之和
设s1表示A1的前缀和,s2表示A2的前缀和
 
n^4的DP方程很好想:f[i][j]表示A1还剩i个,A2还剩j个
有:f[i][j]=min{f[q][p]+(s1[q]-s1[i-1])*(s2[p]-s2[j-1])}
 
n^3:把含前缀和的表达式展开,发现最优的情况每次要么上面只取一个,要么下面只取一个,
于是可以把状态转移方程优化成:
f[i][j]=min{f[k][j+1]+(s1[k]-s1[i])*A1[j+1] , f[i+1][l]+(s2[l]-s2[j])*A2[i+1]},k>i,l>j
 
后来我没看懂题解,乱搞了一个优化,A掉了:
g[i][j]表示(i,j)这个状态的最优决策的第一维
h[i][j]表示(i,j)这个状态的最优决策的第二维
打表发现,g[i][j]随着i的增加而增加(或不变),h[i][j]随着j的增加而增加(或不变)
因此每次i只需要枚举到g[i+1][j],j只需要枚举到g[i][j+1]
时间复杂度没有变,但是优化了不少,过掉了
 
标算:
现在考虑从f[i][j]转移:
要么上方只取了一个,把下方的加入前面的集合:f[i][j] (+A[i]*B[i+1]) -> f[i][j+1] 
要么下方只取了一个,把上方的加入前面的集合:f[i][j] (+A[i+1]*B[i]) -> f[i+1][j]
要么上下都只取一个(上,下方都新开一个集合):f[i][j] (+A[i+1]*B[i+1]) -> f[i+1][j+1]
这样每一次转移就是O(1)的了
----------------------------------------------------------------------
Date:SuperOjP992
只需要去掉所有的割边,把剩下的每一个连通块算一下代价就好
(每一块的代价是总的个数减去这一块的大小,最后答案要除以二因为是无序的)
----------------------------------------------------------------------
_THIS_IS_END_OF_ARTICLE_

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter