WA#7输出问题求调
查看原帖
WA#7输出问题求调
945720
Wanderer_Wu楼主2025/8/29 11:16

错误原因显示输出了额外的信息

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=17;
struct node{
	int l,r,x,y;
}g[N][N*N][N][N][2][2],pp;
int a[N][N],b[N][N],s[N][N],f[N][N*N][N][N][2][2];//0增 1减 
int n,m,k,cnt,ans,pos,sum,mx=-1e9,x,y,q,opt,w,l,r,mid;
void gt(int &x,int y,node &z,node p){//cout<<"fsd";
	if(x<y)x=y,z=p;
}
signed main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)cin>>a[i][j],s[i][j]=s[i][j-1]+a[i][j];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=k;j++){
			for(int l=1;l<=m;l++){
				for(int r=l;r<=min(m,l+j-1);r++){
					int tmp=s[i][r]-s[i][l-1];
					if(r-l+1==j){
						f[i][j][l][r][0][0]=f[i][j][l][r][0][1]=f[i][j][l][r][1][0]=f[i][j][l][r][1][1]=tmp;
					//	cout<<i<<" "<<j<<" "<<l<<" "<<r<<" : "<<f[i][j][l][r][0][0]<<" "<<f[i][j][l][r][0][1]<<" "<<f[i][j][l][r][1][0]<<" "<<f[i][j][l][r][1][1]<<"\n";
						continue;
					}
					for(int x=1;x<=l;x++){
						for(int y=l;y<=min(r,x+(j-(r-l+1))-1);y++){
							gt(f[i][j][l][r][0][0],f[i-1][j-(r-l+1)][x][y][0][0]+tmp,g[i][j][l][r][0][0],{x,y,0,0});
							gt(f[i][j][l][r][0][0],f[i-1][j-(r-l+1)][x][y][1][0]+tmp,g[i][j][l][r][0][0],{x,y,1,0});
						}
					}
					for(int x=1;x<=l;x++){
						for(int y=r;y<=min(m,x+(j-(r-l+1))-1);y++){
							gt(f[i][j][l][r][0][1],f[i-1][j-(r-l+1)][x][y][0][0]+tmp,g[i][j][l][r][0][1],{x,y,0,0});
							gt(f[i][j][l][r][0][1],f[i-1][j-(r-l+1)][x][y][0][1]+tmp,g[i][j][l][r][0][1],{x,y,0,1});
							gt(f[i][j][l][r][0][1],f[i-1][j-(r-l+1)][x][y][1][0]+tmp,g[i][j][l][r][0][1],{x,y,1,0});
							gt(f[i][j][l][r][0][1],f[i-1][j-(r-l+1)][x][y][1][1]+tmp,g[i][j][l][r][0][1],{x,y,1,1});
						}
					}
					for(int x=l;x<=r;x++){
						for(int y=x;y<=min(r,x+(j-(r-l+1))-1);y++){
							gt(f[i][j][l][r][1][0],f[i-1][j-(r-l+1)][x][y][1][0]+tmp,g[i][j][l][r][1][0],{x,y,1,0});
						}
					}
					for(int x=l;x<=r;x++){
						for(int y=r;y<=min(m,x+(j-(r-l+1))-1);y++){
							gt(f[i][j][l][r][1][1],f[i-1][j-(r-l+1)][x][y][1][0]+tmp,g[i][j][l][r][1][1],{x,y,1,0});
							gt(f[i][j][l][r][1][1],f[i-1][j-(r-l+1)][x][y][1][1]+tmp,g[i][j][l][r][1][1],{x,y,1,1});	
						}
					}
				//	cout<<i<<" "<<j<<" "<<l<<" "<<r<<" : "<<f[i][j][l][r][0][0]<<" "<<f[i][j][l][r][0][1]<<" "<<f[i][j][l][r][1][0]<<" "<<f[i][j][l][r][1][1]<<"\n";
				}
			}
		}
	}
	for(int x=1;x<=n;x++){
		for(int i=1;i<=m;i++){
			for(int j=i;j<=m;j++){
				ans=max(ans,max(max(f[x][k][i][j][0][0],f[x][k][i][j][0][1]),max(f[x][k][i][j][1][0],f[x][k][i][j][1][1])));
				if(f[x][k][i][j][0][0]==ans)pos=x,pp={i,j,0,0};
				if(f[x][k][i][j][0][1]==ans)pos=x,pp={i,j,0,1};
				if(f[x][k][i][j][1][0]==ans)pos=x,pp={i,j,1,0};
				if(f[x][k][i][j][1][1]==ans)pos=x,pp={i,j,1,1};
			}
		}
	}
	node tmp;//cout<<g[2][k][1][1][1][1].l<<" "<<g[2][k][1][1][1][1].r<<" "<<g[2][k][1][1][1][1].x<<" "<<g[2][k][1][1][1][1].y<<"\n";
	while(pp.l){
		//cout<<pos<<" "<<pp.l<<" "<<pp.r<<" "<<pp.x<<" "<<pp.y<<"\n";
		for(int i=pp.l;i<=pp.r;i++)b[pos][i]=1;
		tmp=g[pos][k][pp.l][pp.r][pp.x][pp.y],k-=(pp.r-pp.l+1),pos--,pp=tmp;
	}
	cout<<"Oil : "<<ans;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)if(b[i][j])cout<<"\n"<<i<<" "<<j;
	}
	return 0;
}
2025/8/29 11:16
加载中...