CF41D Pawn
link
题意
给定一个矩阵，从底走到顶，每次可以向左上或右上移动，求路径上数字和最大且使 \(M\) 可整除，无解输出 -1。\(1\leq n,m\leq 100,a_{i,j}\in [0,9]\)。
题解
如果没有模 \(k+1\) 的限制的话就是个朴素的二维 dp。有了限制考虑加上一维 \(k\) 表示和模 \(M\) 等于 \(k\)。所以 \(f_{i,j,k}=\max(f_{i,j,k},f_{i+1,j-1,p}+a_{i,j},f_{i+1,j+1,p}+a_{i,j})\)，其中 \(p\) 是和去掉 \(a_{i,j}\) 的余数。还要求输出方案数，倒着推回去就行。复杂度 \(O(nmk)\)。aclink。
坑
- 注意 \(p=(k-a_{i,j}\bmod M+M)\bmod M\)，以防止有负数。
- 注意特判超出边界的各种情况。
代码
#include<bits/stdc++.h>
#define i64 long long
#define L(a,b,c,d) for(int a=b;a<=c;a+=d)
#define R(a,b,c,d) for(int a=b;a>=c;a-=d)using namespace std;
const int N=105;void solve();
int n,m,M,a[N][N],f[N][N][N];signed main(){int Test=1;
// scanf("%d",&Test);while(Test--) solve();return 0;
}void solve(){scanf("%d%d%d",&n,&m,&M);M+=1;L(i,1,n,1){char s[N];scanf("%s",s+1);L(j,1,m,1) a[i][j]=s[j]-'0';}memset(f,255,sizeof f);L(j,1,m,1) f[n][j][a[n][j]%M]=a[n][j];R(i,n-1,1,1){L(j,1,m,1){L(k,0,M-1,1){int p=(((k-a[i][j])%M)+M)%M;if(j>1&&f[i+1][j-1][p]!=-1) f[i][j][k]=max(f[i][j][k],f[i+1][j-1][p]+a[i][j]);if(j<m&&f[i+1][j+1][p]!=-1) f[i][j][k]=max(f[i][j][k],f[i+1][j+1][p]+a[i][j]);}}}int x=0;L(j,1,m,1){if(f[1][j][0]>f[1][x][0]) x=j;}if(f[1][x][0]<0){printf("-1\n");return;}printf("%d\n",f[1][x][0]);int k=0,p=0,j=x;vector<char> ans;L(i,1,n-1,1){p=(((k-a[i][j])%M)+M)%M;if(j==1) ans.push_back('L'),j++;else if(j==m) ans.push_back('R'),j--;else if(f[i][j][k]==f[i+1][j-1][p]+a[i][j]) ans.push_back('R'),j--;else ans.push_back('L'),j++;k=p;}printf("%d\n",j);reverse(ans.begin(),ans.end());for(char c:ans) printf("%c",c);
}