•  
  • 数据结构和算法
  • Noi 01炮兵阵地 & poj1185 &NYOJ81 炮兵阵地 状态压缩、动态规划、滚动数组

Noi 01炮兵阵地 & poj1185 &NYOJ81 炮兵阵地 状态压缩、动态规划、滚动数组

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 03 月 15 日

题目:http://acm.nyist.net/JudgeOnline/problem.php?pid=81

/*为大家方便明白,注释比较多。该题可深化动态规划,学会滚动数组,状态压缩等知识。*/  
#include<iostream>  
#include <string.h>  
using namespace std;  
char map[101][11];//地图  
int surface[101];//地形状态压缩数  
int state[61];//所有的合法状态压缩数  
int stanum[61];//相应状态的炮兵数量  
int f[101][61][61];//动态规划存储矩阵  
int main()  
{  
    int xx;  
    cin>>xx;  
    while(xx--)  
    {  
    memset(map,0,sizeof(map));  
    memset(surface,0,sizeof(surface));  
    memset(state,0,sizeof(state));  
    memset(stanum,0,sizeof(stanum));  
    memset(f,0,sizeof(f));  
    int row,col;  
    cin>>row>>col;  
    for (int i=0;i<row;i++)  
            cin>>map[i];  
    /*因为最大列数不大于10,故可用dp进行状态压缩 
    注:所谓状态压缩即如:PHPP 可以用二进制0100表示,用十进制存储为4。 
    本题因其反向对称性,为了方便压缩,故上边实例压缩成0010,用2表示,不影响求解。*/  
    for (int i=0;i<row;i++)  
        for (int j=0;j<col;j++)  
        {  
            if(map[i][j] == 'H') surface[i] +=1<<j;  
        }  
    /*同地图状态压缩,对排列阵型的状态进行压缩,并算出相应阵型的数量。 
    //如PHPP有0001 0010 1000 1001 摆法,相应的压缩为 1 2 6 7 相关人数为 1 1 1 2*/  
    int snum=0;  
    for(int i=0;i< 1<<col;i++)  
    {  
        int temp=i;  
        if( (i<<1)&i || (i<<2)&i ) continue;  
        stanum[snum] = temp%2;  
        while (  temp = (temp>>1) ) stanum[snum] += temp%2;  
        state[snum++]=i;  
    }  
    /*动态规划状态转移方程: 
    //f[i][j][k] = max{f[i-1][k][l]+stanum[j]},  
    //f[i][j][k]表示第i行状态为s[j],第i-1行状态为s[k]的最大炮兵数 
    //枚举l的每种状态,且state[j],state[k],state[l],地形互不冲突*/  
    //第一行放置所有炮兵情况  
    for (int i=0;i<snum;i++)  
    {  
        /*该处就表现出状态压缩的强大好处了,下边的语句进行状态和地形的判断 
        //仅仅进行一次位与操作,即可知道是否摆放与地形冲突。以后状态判断类似*/  
        if(state[i] & surface[0]) continue;  
        f[0][i][0]=stanum[i];  
    }  
    //第二行放置所有炮兵情况  
    for (int i=0;i<snum;i++)  
    {  
        if(state[i] & surface[1]) continue;  
        for (int k=0;k<snum;k++)  
        {  
            if(state[k] & surface[0]) continue;  
            if(state[i] & state[k]) continue;  
            f[1][i][k] = f[1][i][k] > (f[0][k][0]+stanum[i]) ? f[1][i][k] : (f[0][k][0]+stanum[i]) ;   
        }  
    }  
    //之后的炮兵放置情况。如果还是不明白,请仔细揣摩上边给出的动态规划状态转移方程  
    for (int i=2;i<row;i++)  
        for (int j=0;j<snum;j++)  
        {  
            if(surface[i] & state[j]) continue;  
            for(int k=0;k<snum;k++)  
            {  
                if(surface[i-1] & state[k]) continue;  
                if(state[j] & state[k]) continue;  
                for (int l=0;l<snum;l++)  
                {  
                    if(state[l] & surface[i-2]) continue;  
                    if(state[j] & state[l] || state[k] & state[l]) continue;  
                    f[i][j][k] = f[i][j][k] > (f[i-1][k][l]+stanum[j]) ?   
                        f[i][j][k] : (f[i-1][k][l]+stanum[j]) ;  
                }  
            }  
        }  
    //找出最优解  
    if(row ==0 ) cout<<"0"<<endl;  
    else  
    {  
        int max=0;  
        for (int i=0;i<snum;i++)  
            for (int j=0;j<snum;j++)  
            {  
                if(max<f[row-1][i][j]) max=f[row-1][i][j];  
            }  
            cout<<max<<endl;  
    }  
    }  
    return 0;  
}  
/*另附网上经典的一个使用滚动数组的算法,以上算法为了方便大家阅读和理解,故进行分解演示。 
//明白该题核心算法之后,可以进一步优化,使用滚动数组。其依据为炮兵攻击范围上下2行,所以 
//任意行只与其相邻的两行相互影响,所以创建一个f[2][61][61]的滚动数据即可求解。 
//用滚动数组依次求出每行的最优解 
//roll为当前行,(roll+1)%2为前一行也即下一行 
//roll = 0; 
//for ( int i = 0; i < row; i++ ){ 
//  for ( int j = 0; j < snum; j++ ){ 
//      if ( (state[j]&surface[i]) ) continue;      //状态j是否与i行地图冲突 
//      if ( i == 0 ) f[roll][j][0] = stanum[j]; 
//      else if ( i == 1 ){                     
//          for ( int k = 0; k < snum; k++ ){ 
//              if ( (state[k]&surface[i-1]) ) continue; 
//              if ( (state[j]&state[k]) ) continue; 
//              if ( f[roll][j][k] < f[(roll+1)%2][k][0]+stanum[j] ) 
//                  f[roll][j][k] = f[(roll+1)%2][k][0]+stanum[j]; 
//          } 
//      } 
//      else{ 
//          for ( int k = 0; k < snum; k++ ){ 
//              if ( (state[k]& surface[i-1]) ) continue;       //状态k是否与i-1行地图冲突 
//              if ( state[j]&state[k] ) continue;              //状态j、k是否彼此冲突 
//              for ( int l = 0; l < snum; l++ ){ 
//                  if ( (state[l]& surface[i-2]) ) continue;       //状态l是否与i-2行地图冲突 
//                  if ( (state[j]&state[l]) || (state[k]&state[l]) ) continue;     //状态j、l、k是否彼此冲突 
//                  if ( f[roll][j][k] < f[(roll+1)%2][k][l]+stanum[j] ) 
//                      f[roll][j][k] = f[(roll+1)%2][k][l]+stanum[j]; 
//              } 
//          } 
//      } 
//  } 
//  roll = (roll+1)%2; 
//} 
//roll = (roll+1)%2;*/ 

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日