c++&oi
培训作业-第六周(DP++<2>)
由于明天就要上下个星期一的课了,这个星期就算就此结束了。
总结一下,这个星期主要是完成一套DP练习题。4题150分钟。
现场考的时候大悲剧245/400,据说省队水平基本上是300+。
第
一题 钓鱼 各种边界挂掉,WA了三个点。
第二题
旅游路线 唯一AC的一道题,树形DP。
第三题 Ticket Office 觉得是O(n)DP但不会写,于是贪心55/100
第四题 广场铺砖 状态压缩DP,竟然来不及思考了,果断些了无解和n=2的情况,20/100.
第三题是ceoi2005的题,
貌似比原题简单,我后来写了一个显然会漏解的DP 90/100
按照网上所说的贪心方法写80/100,
仔细想想应该是贪心+DP,但怎么调不是80就是90,于是放弃了
实在不值得。。。
第四题貌似当场有1h也想不出来。
一开始想的是用1表示横放,2表示竖放,0表示被占据
后来发现虽然是O(3^n)的状态数,但三进制不能操作,转移必挂。
让后又想出了记录两行的O(2^(2*n))的状态数,
经过dfs试验只有10000多种状态,虽然远小于2^22但还是会挂。
于是终于才知道只要用一行的0/1储存就行了,不过转移时要顺带算出下一行的。
于是O(h*(2^(w))^2)算法形成了。
实现时用主动更新的方法。用DFS实现局部。
第4题代码
#include
<
cstdio
>
#include
<
cstring
>
#include
<
fstream
>
#include
<
iostream
>
#include
<
algorithm
>
using
namespace
std;
#define
MM(a,i) memset(a,i,sizeof(a))
#define
FOR(i,a,b) for(int i=a;i<=b;i++)
#define
DFOR(i,b,a) for(int i=b;i>=a;i--)
const
int
INF
=~
0U
>>
2
;
#define
int64 long long
int64 F[
12
][
2048
];
ifstream fin(
"
floor.in
"
);
ofstream fout(
"
floor.out
"
);
int
n,m;
void
dfs(
int
i,
int
s1,
int
s2,
int
d);
int
main()
{
fin
>>
n
>>
m;
MM(F,
0
);
F[
0
][
0
]
=
1
;
FOR(i,
0
,n
-
1
)FOR(j,
0
,(
1
<<
m)
-
1
)
if
(F[i][j])dfs(i,j,j,
0
);
fout
<<
F[n][
0
];
return
0
;
}
void
dfs(
int
i,
int
s1,
int
s2,
int
d)
{
if
(d
==
m)F[i
+
1
][s2]
+=
F[i][s1];
else
if
(
!
(s2
&
(
1
<<
d)))
{
dfs(i,s1,s2
|
(
1
<<
d),d
+
1
);
//
将第d位变为1,并右移1位
if
(d
<
m
-
1
&&!
(s2
&
(
1
<<
(d
+
1
))))dfs(i,s1,s2,d
+
2
);
//
如果第d+1位也为0,则直接搜索d+2位
}
else
dfs(i,s1,s2
&~
(
1
<<
d),d
+
1
);
//
将第d位变为0,并右移1位
}
后面到期中考试两周基本上是连着的,一者要AC USACO,二者再顺带总结一下DP。
posted on 2012-03-30 23:28
zyn.cpp
阅读(204)
评论(0)
编辑
收藏
引用
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
<
2012年5月
>
日
一
二
三
四
五
六
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
9
导航
C++博客
首页
新随笔
联系
聚合
管理
统计
随笔 - 57
文章 - 13
评论 - 11
引用 - 0
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔档案
(57)
2012年6月 (2)
2012年5月 (4)
2012年4月 (18)
2012年3月 (7)
2012年2月 (14)
2012年1月 (3)
2011年12月 (8)
2011年11月 (1)
文章档案
(13)
2012年2月 (1)
2011年12月 (7)
2011年11月 (1)
2011年9月 (3)
2011年8月 (1)
搜索
最新评论
1. re: 培训作业-第三周(STL&USACO+4)
评论内容较长,点击标题查看
--佛教网
2. re: 培训作业-第三周(STL&USACO+4)
评论内容较长,点击标题查看
--happem
3. re: NOIP2011解题报告
sum[i]表示前i个点的单位数?这。。,sum[i]表示i点前下车的乘客数吧?
--锐
4. re: NOIP2011解题报告
顶一下。。
--锐
5. re: 培训作业-第三周(STL&USACO+4)
@zyn.cpp
用vector暴力平衡树啊。。。
--姚京韬
阅读排行榜
1. NOIP2011普及组的第三题:瑞士轮(2619)
2. NOI LINUX 安装记(1970)
3. 随便说说状态压缩(1528)
4. 迎接初中同学——整理OI知识点(building)(803)
5. POJ 1733 (551)
评论排行榜
1. 培训作业-第三周(STL&USACO+4)(5)
2. NOIP2011普及组的第三题:瑞士轮(2)
3. POJ 1733 (1)
4. 给count-base sort正身(0)
5. 奇怪的乘法运算(cm)(0)
Powered by:
C++博客
Copyright © zyn.cpp