服了滚动数组洛谷上能过这里60

看题解优化

只展示60的代码洛谷能过最慢139ms

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) x&-x
const int INF=0x3f3f3f3f3f3f3f3f;
const int N=5e2+10;
const int M=2e6+10;
vector<int>g[N];
int n,m,mm;
int a[N][N];
int dp[2][N][N];
int ans;
void solve(){
	cin>>n>>m>>mm;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char x;
			cin>>x;
			if(x=='1'){
				a[i][j]=1;
			}else if(x=='0'){
				a[i][j]=0;
			}else{
				a[i][j]=2;
			}
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<=mm;j++){
			dp[0][i][j]=-INF;
			dp[1][i][j]=-INF;
		}
	}
	if(a[1][1]==2){
		dp[1][1][0]=0;
		dp[1][1][1]=1;
	}else{
		dp[1][1][0]=a[1][1];
	}
	for(int i=1;i<=n;i++){
		int cur=i%2;
		for(int j=1;j<=m;j++){
			if(i==1&&j==1)	continue;
			for(int k=0;k<=mm;k++){
                dp[cur][j][k]=-INF;
            }
			if(a[i][j]==2){
				for(int k=0;k<=mm;k++){
					if(i>1) dp[cur][j][k]=max(dp[cur][j][k],dp[1-cur][j][k]);
					if(i>1&&k-1>=0)	dp[cur][j][k]=max(dp[cur][j][k],dp[1-cur][j][k-1]+1);//变
					if(j-1>=1)	dp[cur][j][k]=max(dp[cur][j][k],dp[cur][j-1][k]);
					if(j-1>=1&&k-1>=0)	dp[cur][j][k]=max(dp[cur][j][k],dp[cur][j-1][k-1]+1);//变
				}
			}else{
				for(int k=0;k<=mm;k++){
					if(i>1)	dp[cur][j][k]=max(dp[cur][j][k],dp[1-cur][j][k]+a[i][j]);
					if(j-1>=1)	dp[cur][j][k]=max(dp[cur][j][k],dp[cur][j-1][k]+a[i][j]);
				}
			}
		}
	}
	ans=0;
	int cur=n%2;
	for(int i=0;i<=mm;i++){
		ans=max(ans,dp[cur][m][i]);
	}
	cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		solve();
	}
    return 0;
}