infinity

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  36 随笔 :: 0 文章 :: 25 评论 :: 0 Trackbacks
http://acm.pku.edu.cn/JudgeOnline/problem?id=1185
经典的状态DP,做了好久才搞定。。。。
先DFS处每行能放置的情况,并记录下来,再用DP,状态是二维的。

dp方程中 ans[i][j][k]表示第i行选第j种状态 第i-1行选第j种状态时的
合法方案总数。

那么ans[i][j][k]=MAX{ans[i-1][k][l]}+one[i][j]
      {    l为枚举第i-2行所选的状态,且该状态能ans[i][j][k]的状态相容
           one[i][j]表示第i行的j种状态种1的个数   }
最后的最大值即最终能放置的最多炮数ret=max{ans[i][j][k]};

 

 

Source Code

Problem: 1185
User: lovecanon
Memory: 1700K
Time: 188MS
Language: C++
Result: Accepted
  • Source Code
  •     

    #include<stdio.h>
    #include
    <string.h>
    #include
    <stdlib.h>

    int R,C;
    int map[101][11];
    int State[101][61];
    int One[101][61];
    int NumOfState[101];
    int ans[101][61][61];
    void init()
    {
        
    int i,j;
        scanf(
    "%d%d",& R,&C);getchar();
        
    for(i=1;i<=R;i++)
        {
            
    for(j=1;j<=C;j++)
                map[i][j]
    =(getchar()=='H');
                getchar();
        }
    }
    void DFS(int CntR,int CntCol,unsigned int CntState,int CountOfOne,int *flag)
    {
        
    if(CntCol>C){State[CntR][++NumOfState[CntR]]=CntState;One[CntR][NumOfState[CntR]]=CountOfOne; return ;}
        
    if(map[CntR][CntCol]==1||(CntCol-1>=1&&flag[CntCol-1]==1||(CntCol-2>=1&&flag[CntCol-2]==1)))
        {

        

            flag[CntCol]
    =0;DFS(CntR,CntCol+1,CntState<<1,CountOfOne,flag);return ;//


        }
        flag[CntCol]
    =0;DFS(CntR,CntCol+1,CntState<<1,CountOfOne,flag);
        flag[CntCol]
    =1;DFS(CntR,CntCol+1,(CntState<<1)+1,CountOfOne+1,flag);
    }

    int main()
    {
        
    int i,j,k,l,ret=0;
        init();
        memset(NumOfState,
    0,sizeof(NumOfState[0]));
        
    for(i=1;i<=R;i++)
        {
            
    int flag[11]={0};
            DFS(i,
    1,0,0,flag);
        }
        ret
    =One[1][NumOfState[1]];
        
    for(i=1;i<=NumOfState[2];i++)
        {
            
    for(j=1;j<=NumOfState[1];j++)
            {
                ans[
    2][i][j]=0;
                
    if((State[2][i]&State[1][j])==0) ans[2][i][j]=One[2][i]+One[1][j];
                
    if(ans[2][i][j]>ret)  ret=ans[2][i][j];
            }
        }

        
    for(i=3;i<=R;i++)
            
    for(j=1;j<=NumOfState[i];j++)
                
    for(k=1;k<=NumOfState[i-1];k++)
                {
                    
    int max=0;
                    
    for(l=1;l<=NumOfState[i-2];l++)
                    {
                         
    if((( State[i - 2][l]^State[i - 1][k])&State[i][j]) == 0)//check if it is valid
                             if(ans[i-1][k][l]>max)  max=ans[i-1][k][l];
                        
    //if((State[i-2][l]&State[i-1][k])==0&&(State[i-1][k]&State[i][j])==0&&(State[i-2][l]&State[i][j])==0)
                        
    //    if(ans[i-1][k][l]>max)  max=ans[i-1][k][l];
                    }
                    ans[i][j][k]
    =max+One[i][j];
                    
    if(ans[i][j][k]>ret)  ret=ans[i][j][k];
                }
        printf(
    "%d\n",ret);
        
    return 0;
    }

posted on 2008-09-20 04:09 infinity 阅读(2188) 评论(5)  编辑 收藏 引用 所属分类: acm

评论

# re: poj 1185 炮兵阵地 2009-05-17 13:55 young,bobby
大哥 您的程序真的错了 试试这组数据
100 10
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
你的答案是392 正确的答案是330 网上其它人ac的程序答案也是330 可是你的程序竟然ac了 。。。。。想不明白
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP  回复  更多评论
  

# re: poj 1185 炮兵阵地 2009-05-17 14:01 还是我
大哥 您的程序真的错了 试试这组数据
100 10
HHHHHHHHHH
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
PPPPPPPPPP
你的答案是392 正确的答案是330 网上其它人ac的程序答案也是330 可是你的程序竟然ac了 。。。。。想不明白 人品???
大家注意  回复  更多评论
  

# re: poj 1185 炮兵阵地[未登录] 2009-05-20 13:08 infinity
可能吧 我有时间再看看  回复  更多评论
  

# re: poj 1185 炮兵阵地 2009-12-02 22:46 iloveyty
sometimes ,rp is really a very importtant thing  回复  更多评论
  

# re: poj 1185 炮兵阵地 2011-05-13 09:51 dwang
线段树  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理