小阮的菜田
一个人一种命,各安天命吧。
C++博客
首页
新随笔
联系
聚合
管理
随笔-141 评论-9 文章-3 trackbacks-0
USACO 3.2.2 Stringsobits (DP)
DP
f[i][j] 表示长度为i 的01串,1的个数不多于j的个数。
则对于第i位是0还是1,可分为两个子状态 f[i][j] = f[i-1][[j] + f[i-1][j-1]
/**/
/*
ID: lorelei3
TASK: kimbits
LANG: C++
*/
#include
<
fstream
>
using
namespace
std;
long
long
N,L,I;
long
long
f[
100
][
100
];
int
main()
{
int
i,j;
ifstream fin(
"
kimbits.in
"
);
ofstream fout(
"
kimbits.out
"
);
fin
>>
N
>>
L
>>
I;
for
(i
=
0
; i
<=
N;
++
i)
f[
0
][i]
=
f[i][
0
]
=
1
;
for
(i
=
1
; i
<=
N;
++
i)
for
(j
=
1
; j
<=
N;
++
j)
f[i][j]
=
f[i
-
1
][j]
+
f[i
-
1
][j
-
1
];
for
(i
=
N; i
>=
1
;
--
i)
if
(I
>
f[i
-
1
][L])
{
fout
<<
"
1
"
;
I
-=
f[i
-
1
][L];
--
L;
}
else
fout
<<
"
0
"
;
fout
<<
endl;
return
0
;
}
posted on 2010-12-22 13:03
小阮
阅读(337)
评论(0)
编辑
收藏
引用
所属分类:
USACO
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
USACO_MAR11 Spiral (螺旋矩阵, 模拟)
USACO 6.1.2 A Rectangular Barn (最大子矩阵, DP)
USACO 6.1.1 Postal Vans (哈密顿回路, 递推, 高精度计算)
USACO 5.5.3 Two Five (DP)
USACO 5.5.2 Hidden Passwords (后缀数组)
USACO 5.5.1 Picture (离散化)
USACO 5.4.5 TeleCowmunication (最小点割集, Dinic)
USACO 5.4.4 Betsy's Tour (DFS+剪枝)
USACO 5.4.3 Character Recognition (DP)
USACO 5.4.2 Canada Tour (DP)
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
<
2010年12月
>
日
一
二
三
四
五
六
28
29
30
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
31
1
2
3
4
5
6
7
8
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(1)
给我留言
查看公开留言
查看私人留言
随笔分类
C++程序设计语言(6)
POJ(13)
USACO(97)
计算几何(5)
数据结构和算法(20)
网络编程(1)
随笔档案
2011年10月 (2)
2011年6月 (3)
2011年5月 (2)
2011年4月 (6)
2011年3月 (17)
2011年2月 (25)
2011年1月 (24)
2010年12月 (28)
2010年11月 (34)
文章档案
2011年2月 (3)
搜索
最新评论
1. re: USACO 4.2.3 Job Processing (平均贪心)
如何证明其正确性
--膜
2. re: USACO 5.2.2 Electric Fences (模拟退火算法)[未登录]
666@匿名
--xixi
3. re: USACO 2.3.1 The Longest Prefix [未登录]
发现一个错误,对于测试实例
AE ABC CDEF .
ABCDEFG
错误
正确答案是3
--z
4. re: USACO 4.2.3 Job Processing (平均贪心)
平均的贪心,好像没听说诶。
--怡红公子
5. re: USACO 5.4.2 Canada Tour (DP)
不明白如何去除重复的,就是怎么解决两个人交叉问题?
--zyz913614263
阅读排行榜
1. 计算几何 - 判断线段相交(转)(3661)
2. N个点中求三个点组成的三角形面积最大(2034)
3. [网络流]最小路径覆盖问题 (二分图最大匹配, 最大流)(1693)
4. ural 1297 最长回文子串(后缀数组)(1677)
5. [网络流] 方格取数问题 ( 二分图点权最大独立集, 最小割模型, 最大流)(1352)
评论排行榜
1. USACO 5.2.2 Electric Fences (模拟退火算法)(3)
2. USACO 4.2.3 Job Processing (平均贪心)(2)
3. pku 1948 Triangular Pastures (01背包)(1)
4. USACO 2.3.1 The Longest Prefix (1)
5. pku 1625 Censored! (AC自动机, DP, 高精度加法)(1)