90分,第一个点(就是样例)wa了,求助
查看原帖
90分,第一个点(就是样例)wa了,求助
153972
hhdddkk楼主2020/7/24 21:19

本地跑出来是对的6,但评测下来不对,是代码里有什么未定义行为吗

#include<bits/stdc++.h>
using namespace std;
int m,n;
int dp[3][(1<<10)][(1<<10)];
char mp[101][11];
int ans;
bool vis[3][(1<<10)][(1<<10)],v[1<<10];
inline bool Check(int l,int st,int pre){
	if(st&pre) return false;
	for(int i=0;i<m;i++){	
		if(st&(1<<i)){
			if(mp[l][i+1]=='H') return false;
		}
		if(pre&(1<<i)){
			if(mp[l-1][i+1]=='H') return false;
		}
	}
	vis[l%2][st][pre]=1;
	int t=st;
	while(t){
	    dp[l%2][st][pre]++;
	    t=t-(t&-t);
    }
    if(l==2){
    	int cnt=0;
    	int t=pre;
    	while(t){
    		cnt++;
    		t=t-(t&-t);
		}
		dp[0][st][pre]+=cnt;
	}
	return true;
}
inline bool judge(int now,int pre){
	if(now&pre) return false;
	return true;
}
void solve(){
	if(n==1){
		for(int i=1;i<=m;){
			if(mp[1][i]=='H'){
				i++;
				continue;
			}
			ans++;
			i+=3;
		}
	}
	

	    	
	for(register int i=2;i<=n;i++)
	    for(register int j=0;j<=(1<<m)-1;j++){
	    	if(v[j]) continue;
	        for(register int k=0;k<=(1<<m)-1;k++){
	        	if(v[k]) continue;
	        	dp[i%2][j][k]=0;
	        	vis[i%2][j][k]=0;
	        	if(!Check(i,j,k)) continue;
	        	int cnt=dp[i%2][j][k];
	        	dp[i%2][j][k]=0;
	        	for(register int l=0;l<=(1<<m)-1;l++)
	               if(vis[i%2][j][k]&&vis[(i-1)%2][k][l]&&judge(j,l))
	                   dp[i%2][j][k]=max(dp[i%2][j][k],dp[(i-1)%2][k][l]);
				dp[i%2][j][k]+=cnt; 
				ans=max(ans,dp[i%2][j][k]);
			}
		}
	printf("%d",ans);           
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	getchar();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
		    mp[i][j]=getchar();
		getchar();
	}
	for(int i=1;i<(1<<m);i++){
		for(int j=0;j<m;j++){
			if((i&(1<<j))&&j&&(i&(1<<(j-1)))) v[i]=1;
		    if((i&(1<<j))&&j>=2&&(i&(1<<(j-2)))) v[i]=1;
		}
	}
	solve();
	return 0;
}
2020/7/24 21:19
加载中...