链接:https://nanti.jisuanke.com/t/57049
我想暴力dp拿40分,我这个哪里错了呀?
#include<iostream>
#include<cstring>
using namespace std;
int a[505][10],f_r[250005][10],f_l[250005][10],vis[250005][10];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m,k,nn;
int dsfj(int opt,int x,int y){
int sum=0,nx,ny;
for(int i=0;i<4;i++){
nx=x+dx[i];
ny=y+dy[i];
if(nx>=1&&nx<=nn&&ny>=1&&ny<=m&&!vis[nx][ny]){
sum+=(a[nx%n+1][ny]==opt);
vis[nx][ny]=1;
}
}
return sum;
}
int main(){
freopen("Falling.in","r",stdin);
freopen("Falling.out","w",stdout);
cin>>n>>m>>k;
nn=n*k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=nn;i++){
for(int j=1;j<=m;j++){
if(i==1){
f_r[i][j]=dsfj(1,i,j);
continue;
}
if(j==1){
f_r[i][j]=max(f_r[i-1][j]+dsfj(1,i-1,j),f_r[i-1][j+1]+dsfj(1,i-1,j+1))+dsfj(1,i,j);
continue;
}
f_r[i][j]=max(f_r[i-1][j-1]+dsfj(1,i-1,j-1),max(f_r[i-1][j]+dsfj(1,i-1,j),f_r[i-1][j+1]+dsfj(1,i-1,j+1)))+dsfj(1,i,j);
}
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=nn;i++){
for(int j=1;j<=m;j++){
if(i==1){
f_l[i][j]=dsfj(2,i,j);
continue;
}
if(j==1){
f_l[i][j]=max(f_l[i-1][j]+dsfj(2,i-1,j),f_l[i-1][j+1]+dsfj(2,i-1,j+1))+dsfj(2,i,j);
continue;
}
f_l[i][j]=max(f_l[i-1][j-1]+dsfj(2,i-1,j-1),max(f_l[i-1][j]+dsfj(2,i-1,j),f_l[i-1][j+1]+dsfj(2,i-1,j+1)))+dsfj(2,i,j);
}
}
int rmas=0,lmas=0;
for(int i=1;i<=m;i++){
rmas=max(rmas,f_r[nn][i]);
lmas=max(lmas,f_l[nn][i]);
}
cout<<lmas+rmas;
return 0;
}