Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
自认为还可以的代码 AC的哦。。#include "stdio.h" #include "memory.h" int map[102]; int possible[60],N,M,t,length[60],dp[60][60][102]; int main(void) { t=0; int i,k,j,l,max; char c; scanf("%d%d",&N,&M); scanf("\n"); map[0]=map[1]=0; memset(dp,-1,sizeof(dp)); for(i=0;i!=N;++i) { for(j=0;j!=M;++j) if(scanf("%c",&c)==1&&c=='P') map[i+2]+=1<<(M-j-1); scanf("%c",&c); } k=1<<M; for(i=0;i!=k;++i) if(!(i>>1&i||i>>2&i)) possible[t++]=i; for(i=0;i!=t;++i) { k=0; for(j=0;j!=M;++j) if(possible[i]&(1<<j)) k++; length[i]=k; } dp[0][0][1]=0; for(i=1;i!=N+1;++i) { for(j=0;j!=t;++j) { if((possible[j]&map[i])!=possible[j]) continue; for(k=0;k!=t;++k) { max=0; if((possible[k]&map[i+1])!=possible[k]||possible[j]&possible[k]) continue; for(l=0;l!=t;++l) { if((possible[l]&map[i-1])!=possible[l]||possible[j]&possible[l]||possible[k]&possible[l]) continue; max=dp[l][j][i]>max?dp[l][j][i]:max; } dp[j][k][i+1]=max+length[k]; } } } max=0; for(i=0;i!=t;++i) for(j=0;j!=t;++j) max=max<dp[i][j][N+1]?dp[i][j][N+1]:max; printf("%d\n",max); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator