求助 WA on #8
  • 板块CF41D Pawn
  • 楼主WZY718605
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/5/21 20:05
  • 上次更新2023/10/23 15:05:09
查看原帖
求助 WA on #8
365948
WZY718605楼主2023/5/21 20:05
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int n,m,k;
int map1[105][105];
int f[105][105][12],last[105][105][12];
int bx[105],by[105],bz[105],cnt;
int main(){
	char c;
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			c=getchar();
			while(c>'9'||c<'0') c=getchar();
			map1[i][j]=c-'0';
		}
	}
	memset(f,-1,sizeof(f));
	ll ans=-1,idx,idy;
	for (int j=1;j<=m;j++){
		f[n][j][map1[n][j]%(k+1)]=map1[n][j];
		if(f[n][j][0]>ans){
			ans=f[n][j][0];
			idx=n,idy=j;
		}
	}
	for (int i=n-1;i>=1;i--){
		for (int j=1;j<=m;j++){
			for (int x=0;x<=k;x++){
				if(j>1&&f[i+1][j-1][x]>=0){
					if(f[i][j][(x+map1[i][j])%(k+1)]<f[i+1][j-1][x]+map1[i][j]){
						f[i][j][(x+map1[i][j])%(k+1)]=f[i+1][j-1][x]+map1[i][j];
						last[i][j][(x+map1[i][j])%(k+1)]=1;
					}
				}
				if(j<m&&f[i+1][j+1][x]>=0){
					if(f[i][j][(x+map1[i][j])%(k+1)]<f[i+1][j+1][x]+map1[i][j]){
						f[i][j][(x+map1[i][j])%(k+1)]=f[i+1][j+1][x]+map1[i][j];
						last[i][j][(x+map1[i][j])%(k+1)]=2;
					}
				}
			}
			if(f[i][j][0]>ans){
				ans=f[i][j][0];
				idx=i; idy=j;
			}
			/*cout<<i<<" "<<j<<endl;
			for (int x=0;x<=k;x++) cout<<f[i][j][x]<<" ";
			cout<<endl;*/
		}
	}
	if(ans==-1){
		printf("-1\n");
	}
	else{
		//cout<<idx<<" "<<idy<<" "<<endl;
		printf("%d\n",ans);
		while(idx<=n){
			//cout<<idx<<" "<<idy<<" "<<ans<<endl;
			bx[++cnt]=idx; by[cnt]=idy; bz[cnt]=ans%(k+1);
			if(last[idx][idy][ans%(k+1)]==1){
				ans-=map1[idx][idy];
				idx++; idy--;
			}
			else{
				ans-=map1[idx][idy];
				idx++; idy++;
			}
		}
		printf("%d\n",by[cnt]);
		for (int i=cnt-1;i>=1;i--){
			if(last[bx[i]][by[i]][bz[i]]==1) putchar('R');
			else putchar('L');
		}
	}
	return 0;
}
2023/5/21 20:05
加载中...