longshen
C++博客
首页
联系
聚合
管理
随笔 - 26 文章 - 6 trackbacks - 0
<
2009年9月
>
日
一
二
三
四
五
六
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(3)
给我留言
查看公开留言
查看私人留言
随笔分类
acm总结(3)
ASP.NET(1)
p2p(1)
poj(7)
VC++(6)
程序员(7)
随笔档案
2011年10月 (1)
2010年12月 (1)
2010年9月 (1)
2010年4月 (4)
2009年11月 (4)
2009年9月 (1)
2009年7月 (5)
2009年5月 (6)
2009年4月 (3)
朋友
cqh
大学室友...
搜索
最新评论
1. re: acm博弈题 -- 个人小结[未登录]
1730用博弈论是怎么做的?
--zj
2. re: acm博弈题 -- 个人小结
楼主,你的博文中有一处错误, ((+)为 按位与)是错的,(+)应该为按位异或
--913614263@qq.com
3. re: 解决 error LNK2019: 无法解析的外部符号 问题
InternetGetCookieA
在用wininet库吧。
--张
4. re: poj 1947 Rebuilding Roads -- 树形DP
good~好代码,膜拜
--czy
5. re: ACM总结 -- 退役贴
ym~
--july
阅读排行榜
1. 解决 error LNK2019: 无法解析的外部符号 问题(50245)
2. ACM总结 -- 退役贴(4783)
3. acm博弈题 -- 个人小结(3077)
4. poj 1947 Rebuilding Roads -- 树形DP(2246)
5. poj 1191 棋盘分割 -- 动态规划(1578)
评论排行榜
1. poj 1947 Rebuilding Roads -- 树形DP(2)
2. acm博弈题 -- 个人小结(2)
3. 解决 error LNK2019: 无法解析的外部符号 问题(1)
4. ACM总结 -- 退役贴(1)
5. Unicode与多字节的基本运用 -- Windows编程(0)
poj 1837 Balance -- 动态规划
#include
<
iostream
>
#define
MAX 22
using
namespace
std;
const
int
mm
=
8000
;
int
dp[MAX][mm
+
mm];
int
arm[MAX], w[MAX];
/**/
/*
dp[i][mm+k]:取前i个时,天平处于k状态的方法数
mm+k: < mm为左边重, > mm 为右边重
dp[i][mm+k] +=
dp[i-1][mm + k-weight[i]*arm[j]], (j:1->c)};
*/
int
main()
{
int
c, g, i, j, k;
while
(cin
>>
c
>>
g)
{
for
(i
=
0
; i
<
c; i
++
)
cin
>>
arm[i];
for
(i
=
0
; i
<
g; i
++
)
cin
>>
w[i];
memset(dp,
0
,
sizeof
(dp));
for
(j
=
0
; j
<
c; j
++
)
dp[
0
][mm
+
arm[j]
*
w[
0
]]
=
1
;
for
(i
=
1
; i
<
g; i
++
)
{
for
(k
=
-
mm; k
<=
mm; k
++
)
{
int
sum
=
0
;
for
(j
=
0
; j
<
c; j
++
)
if
(k
-
arm[j]
*
w[i]
>=
-
mm
&&
k
-
arm[j]
*
w[i]
<=
mm)
sum
+=
dp[i
-
1
][mm
+
k
-
arm[j]
*
w[i]];
dp[i][mm
+
k]
=
sum;
}
}
cout
<<
dp[g
-
1
][mm]
<<
endl;
}
return
0
;
}
posted on 2009-05-15 09:53
longshen
阅读(483)
评论(0)
编辑
收藏
引用
所属分类:
poj
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
poj 3254 Corn Fields -- 状态压缩DP
poj 1947 Rebuilding Roads -- 树形DP
poj 1837 Balance -- 动态规划
poj 2192 Zipper -- 简单DP
poj 2186 Popular Cows -- 强连通分支
poj 2762 Going from u to v or from v to u? -- 强连通
poj 1191 棋盘分割 -- 动态规划
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理