AC这道牛B的题目,开心。虽然WA了4次,RE了2次。
1.算法
经典的状态压缩动态规划题。让我慢慢道来:
(1)首先,看到这个题目想到的是暴力搜索,无所谓深搜还是宽搜,都需要对所有的情况进行穷举,10*100的格子,这样穷举的话基本上会超时。想到用贪心法,但是贪心法的结果是不正确的。
(2)于是想到动态规划,动态规划的重点是找状态转移方程,需要状态记录的数组f(因为最终要求的是大炮个数,所以f的值记录当前状态的大炮个数)。从题目的数据中来看因为m<10,所以以行划分状态比较合理,这样有n行,就用记录状态的数组f的第一个下标记录行号。因为本题的大炮的射程是2格,所以,第i行和他的前两行都有关系,也就是说第i行的状态要根据前两行的状态来得到而不是前一行,于是在记录状态的时候要记录两行的状态(思考为什么),这样,f数组的第二个下标和第三个下标分别是第i行的状态和第i-1行的状态。这样可以列出状态转移的方程式:f[i][x][y]=max{f[i-1][y][z]}+c[x] (其中z为i-2行所有的状态,c[x]为x状态中的大炮的个数)
(3)有个状态转移方程这个精髓,就来说说这个题目的实现了:
a.读入数据n,m和矩阵数据,并且把每一行的数据以2进制的形式(有山处为1,平原处为0)保存为一个int类型,即row数组。(read_in函数)
b.因为同一行的大炮不能相互射击,所以可以把每一行可能的状态列举出来,s表示一行的所有状态,c与s对应,表示对应状态的大炮个数,s_sum是s的大小,即总的状态个数(m最大为10时,一行的状态最多,为60种,于是,数组只要开到60)这些都是为下面的计算节省时间。计算一行可能的所有状态是通过深搜实现的,即dfs函数。(creat_s函数)
c.最重要的动态规划环节,首先判断特例,只有一行时的做法是:将s中所有的状态分别和第一行的状态row[0]做&操作,以判断是否这个状态可以符合只在平原上放大炮的条件。如果&的结果为0,即没有在有山的地方放置大炮,反之则不然。在符合条件的状态中找一个大炮数最多的状态作为返回值。如果不止一行,就对f[1][][]的数组进行操作,第一参数为1表示后面两个参数是第1行和第0行的状态,对第1行的状态(i)和第0行的状态(j)遍历,如果两行均符合平原山地条件以及两行不冲突条件(即两行之间没有大炮能相互攻击),则将f[1][i][j]的值设为c[i]+c[j],否则为0。接着要做的事情是从i=2开始,通过状态转移方程得到后面的所有状态。最后找出最后两行状态的f的最大值,这个值即为所求结果。
2.实现
(1)对于位操作,如果要获得第i位的数据,判断((data&(0X<<i))==0),若真,为0,假,为1;如果要设置第i位为1,data=(data|(0X1<<i));如果要设置第i位为0,data=(data&(~(0X1<<i)));如果要改变第i位,data=(data^(0X1<<i)).
(2)在构建s的时候,通过递归进行深搜。对于深搜的代码要熟练掌握,主要是递归条件和终止条件。
(3)动态规划的时候要注意将特殊情况列出,比如这一题的n=1的情况。
(4)在多重循环的时候要注意剪枝的运用,如if((s[x]&row[i])!=0)continue;这一句就避免了下面的两重循环的时间浪费。
3.代码
Problem: 1185 User: godfrey90
Memory: 1560K Time: 313MS
Language: C++ Result: Accepted
#include<cstdio>
int n,m;
int row[100];//record the read-in data
int s[60];//record the available row status
int c[60];//record each status's number
int s_sum = 0;
int f[100][60][60]={0};
void read_in();
void creat_s();
int dp();
int main(){
read_in();
creat_s();
int result = dp();
printf("%d\n",result);
return 0;
}
void read_in(){
char str[10];
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
scanf("%s",str);
int data = 0;
for(int j=0;j<m;j++){
if(str[j]=='H')
data=data|(0X1<<j);
}
row[i]=data;
}
}
void dfs(int x,int data){
if(x==m){
s[s_sum]=data;
int y=0;
for(int i=0;i<m;i++){
if((data&(0X1<<i))!=0) y++;
}
c[s_sum]=y;
s_sum++;
return;
}
if(((x>0)&&((data&(0X1<<(x-1)))!=0))||((x>1)&&((data&(0X1<<(x-2)))!=0))){
dfs(x+1,data);
}else{
dfs(x+1,data);
dfs(x+1,data|(0X1<<x));
}
}
void creat_s(){
dfs(0,0);
}
int dp(){
int result=0;
if(n==1){
for(int i=0;i<s_sum;i++){
if(((s[i]&row[0])==0)&&(c[i]>result)) return c[i];
}
}
for(int i=0;i<s_sum;i++){
for(int j=0;j<s_sum;j++){
if(((s[i]&row[1])==0)&&((s[j]&row[0])==0)&&((s[i]&s[j])==0)){
f[1][i][j]=c[i]+c[j];
}
}
}
for(int i=2;i<n;i++){
for(int x=0;x<s_sum;x++){
if((s[x]&row[i])!=0)continue;
for(int y=0;y<s_sum;y++){
if((s[x]&s[y])!=0)continue;
for(int z=0;z<s_sum;z++){
if(((s[z]&s[x])!=0)||(f[i-1][y][z]==0))continue;
if(f[i][x][y]<f[i-1][y][z]){
f[i][x][y]=f[i-1][y][z];
}
}
f[i][x][y]+=c[x];
}
}
}
for(int i=0;i<s_sum;i++){
for(int j=0;j<s_sum;j++){
if(f[n-1][i][j]>result)
result = f[n-1][i][j];
}
}
return result;
}
分享到:
相关推荐
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
poj 3720解题报告poj 3720解题报告poj 3720解题报告poj 3720解题报告
poj1691解题报告 题目来源:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691) 解法: 搜索
poj2828解题报告,希望能帮到志同道合的算法爱好者
北大poj解题报告,希望能帮到软件工程的同学,每天一道,持之以恒,熟能生巧,与您共勉!
北大ACM1316解题报告
Problem 1061 青蛙的约会 poj解题报告。有源码。可直接提交C++实现
这是我发的第二篇解题报告,写的不怎么的。呵呵!!!!!
ACM POJ 解题报告北大POJ 大量解题代码
ACM Poj Pku 解题报告答案 打包 下载 600多题 史上最全 不是网上乱传的200多题,更不是100多题就挂着10分才能下的题 下了这个 大家也不要浪费分数去下载其它版本的了,基本上都有 共享 一起进步 中国加油 ACMer...
本人整理的POJ解题报告,一共有250道题
不错的资源 收集了网上的一些解题报告 方便同学们学习参考
北大ACM在线评测系统POJ的题目解题报告。涵盖各种类型的acm题目。值得参考借鉴。打包下载。
2遍dp poj_3613解题报告 poj_3613解题报告