IAML's Blog

Find passion in coding

poj1837 Balance

自从4.11在sysu预选赛充分地感觉到无力之后,有一个多星期患上了赛后综合症,一直不想或者说,逃避编程。经过啊通和龙兄的帮助,终于在一个多星期后的今天重新做了poj的题,也做了sicily的题,总算从阴影中走出。呵呵。只能怪自己太水了,差点就成了:在哪跌倒,就在哪埋了= =。

好了,废话少说,这题的主要难点是找状态存储方法(er,据说所有的dp题都是这样,所以这句有点废= =)。存储方法是m[i][t]表示有i个物品时,总权为t的个数。状态转移方程m[i][t] += m[i-1][j+hook[k]*w[i]],最后只要找出m[g][N]的数目就可以了。

继续阅读