Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

55用了楼大叔PPT的方法，多重背包化0－1和bitset，还是超（代码）

Posted by userfriendly at 2009-02-19 00:47:37 on Problem 1742 and last updated at 2009-02-19 01:06:11

O(NMlgC)

bitset<100010> dp[2];//做滚动数组
v[], vp //做物品代价数组和尾指针

是不是这部分还有什么能挖的？

		for(int i=0; i<vp; i++)
		{
			x=i%2; y=(i+1)%2;
			dp[y]=dp[x];
			for(int j=v[i]; j<=m; j++)
				if(!dp[y][j] && dp[x][j-v[i]])
					dp[y].set(j);
		}


输出dp[y].count()-1

答案是没错的

Followed by:

被楼大叔小骗一下。不要用bitset。。 (174) userfriendly 2009-02-19 02:13:19
- Re:被楼大叔小骗一下。不要用bitset。。 (3) zjut020 2009-09-07 17:14:50
  - Re:被楼大叔小骗一下。不要用bitset。。 (31) 305636397 2010-06-23 20:56:52

Post your reply here:

Home Page Go Back To top