同济校赛|菜哭武的房子（dp）

题目

http://acm.tongji.edu.cn/problem.php?id=1115

题目大意

只能走1，并且只能往前左右走，最多能跨越几行（?)。

算法思路

• dp[i][j]为前i行走到j格时，最多能走的行数。

if s[i][j]=1 : dp[i][j]=dp[i-1][j]
if s[i][j]=0 : dp[i][j]=max(dp[i-1][j]+1,dp[i][j-1])

一行dp结束之后要从右往左回溯一遍，一行有联通块都可以互相到达，前面只算了从左往右走的，没有算从右往左走的。

for(int j=m-1;j>=1;j--){
        if(s[i][j]=='1'&&s[i][j-1]=='1'){
            dp[i][j-1]=max(dp[i][j],dp[i][j-1]);
        }

这样子就好了。

代码

#include<cstdio>
#include<iostream>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define pb(x) push_back(x)
#define fir first
#define sec second
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
const int INF=0x3f3f3f3f;
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
//ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
char s[510][510];
int dp[510][510];
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
   int t;
   cin>>t;int k=0;
   while(t--){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>s[i];
        mem(dp);
    for(int i=1;i<=n;i++){
      for(int j=0;j<m;j++){
        if(s[i][j]=='0'){
            dp[i][j]=dp[i-1][j];
        }
        else{
            dp[i][j]=dp[i-1][j]+1;
            if(j&&s[i][j-1]=='1') dp[i][j]=max(dp[i][j],dp[i][j-1]);
        }
      }
      for(int j=m-1;j>=1;j--){
        if(s[i][j]=='1'&&s[i][j-1]=='1'){
            dp[i][j-1]=max(dp[i][j],dp[i][j-1]);
        }
      }
    }
    int ans=0;
    for(int j=0;j<m;j++)
        ans=max(ans,dp[n][j]);
    cout<<"Case #"<<++k<<":"<<endl;
    cout<<ans<<endl;
   }
}