題目
http://acm.#edu.cn/problem.php?id=1115
題目大意
只能走1，并且只能往前左右走凰狞，最多能跨越幾行（?)。
算法思路
- dp[i][j]為前i行走到j(luò)格時(shí)达布，最多能走的行數(shù)逾冬。
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結(jié)束之后要從右往左回溯一遍躺苦，一行有聯(lián)通塊都可以互相到達(dá)产还，前面只算了從左往右走的，沒有算從右往左走的脐区。
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;
}
}
