http://acm.pku.edu.cn/JudgeOnline/problem?id=1185經(jīng)典的狀態(tài)DP，做了好久才搞定。。。。
先DFS處每行能放置的情況，并記錄下來(lái)，再用DP，狀態(tài)是二維的。
dp方程中 ans[i][j][k]表示第i行選第j種狀態(tài) 第i-1行選第j種狀態(tài)時(shí)的
合法方案總數(shù)。
那么ans[i][j][k]=MAX{ans[i-1][k][l]}+one[i][j]
{ l為枚舉第i-2行所選的狀態(tài)，且該狀態(tài)能ans[i][j][k]的狀態(tài)相容
one[i][j]表示第i行的j種狀態(tài)種1的個(gè)數(shù) }
最后的最大值即最終能放置的最多炮數(shù)ret=max{ans[i][j][k]};
Source Code
| Problem: 1185 |
|
User: lovecanon |
| Memory: 1700K |
|
Time: 188MS |
| Language: C++ |
|
Result: Accepted |
#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;
}