CF41D Pawn 题解

题目链接：CF41D Pawn

题意：国际象棋棋盘最底行站了一个兵。 它只有两种行动方式： 向上左或向上右走。 它可以选择从最低行哪个节点开始他的旅程。 每个格子上有0-9颗豌豆，而士兵想移动到最上一行并且积累到尽可能多的豌豆。同时，因为这个士兵必须把豌豆平均分给自己和他的k个兄弟，他所收集到的豌豆必须是k+1的倍数。请找到他可以收集到的最多豌豆，并确定他的操作序列。

规定士兵不能手动扔出豌豆，并且他必须捡起所到达的每一个格子的所有豌豆。

输入格式： 第一行三个整数 $n,m,k(2 \le n,m \le 100, 0 \le k \le 10)$ 行数、列数、士兵的兄弟们。 接下来一个 $n \times m$ 的矩阵，每个元素均是0-9的整数（不空格），描述该格的豌豆。第一行被认为是最上一行，最后一行被认为是最下一行。

输出格式：

如果不能收集到k+1倍数的豌豆，输出-1. 否则，输出第一行一个整数，为最多豌豆数；第二行一个整数，为士兵开始移动的位置；第三行包括n-1个字母L 或 R，表示士兵的行动序列。

如果有多种收集到相同且是k+1倍数数量的豌豆，你可以任意输出一种方案。

设 $f(i,j,k)$ 为走到第 $i$ 行第 $j$ 列且恰好取了 $k$ 个的方案数

这里不用求方案数，就用bool即可。

不习惯从下往上跑就翻转一下，答案就是 $f(n,j,c)$ ，其中 $c$ 是 $k$ 的倍数。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(115)
int n,m,c;
int a[N][N];
bool dp[N][N][N*10];
char d[N][N][N*10];
void print(int i,int j,int k)
{
    if(i==1)
    {
        printf("%lld\n",j);
        return;
    }
    char di=d[i][j][k];
    if(di=='L')print(i-1,j+1,k-a[i][j]);
    else print(i-1,j-1,k-a[i][j]);
    putchar(d[i][j][k]);
}
signed main()
{
    scanf("%lld%lld%lld",&n,&m,&c);
    for(int i=n; i>=1; i--)
        for(int j=1; j<=m; j++)
            scanf("%1lld",&a[i][j]);
    for(int i=1; i<=m; i++)
        dp[1][i][a[1][i]]=1;
    for(int i=2; i<=n; i++)
        for(int j=1; j<=m; j++)
            for(int k=9*n; k>=a[i][j]; --k)
            {
                if(j-1>=1&&dp[i-1][j-1][k-a[i][j]])
                {
                    dp[i][j][k]|=dp[i-1][j-1][k-a[i][j]];
                    d[i][j][k]='R';
                }
                if(j+1<=m&&dp[i-1][j+1][k-a[i][j]])
                {
                    dp[i][j][k]|=dp[i-1][j+1][k-a[i][j]];
                    d[i][j][k]='L';
                }
            }
    for(int k=(9*n/(c+1))*(c+1); k>=0; k-=c+1)
        for(int i=1; i<=m; i++)
            if(dp[n][i][k])
            {
                printf("%lld\n",k);
                print(n,i,k);
                return 0;
            }
    puts("-1");
    return 0;
}