简单DP

工作了太无聊了，看了下周赛，顺便写写题。
题很简单，按照题意正常写DP即可。
首先数据范围很小，100 * 100 * 10 = 1e5
可以考虑DP(某些时候可以从数据量反推算法)
考虑怎么设置数组来表示状态
切入点是余数。
我们可以想到可以设置DP[i][j][p]
表示当前这个位置，积分和%(k + 1) == p 的情况
因为只是要求总积分%(k + 1) == 0
所以在转移时无需其他处理（有一些相似的题要求每一步都能整除）
最后直接输出 最后一行%（k + 1）== 0的最佳方案即可

#include<bits/stdc++.h>
using namespace std;

const int N = 1e2 + 5;
typedef pair<int , string>pis;
pis dp[N][N][12];
int mp[N][N];
int n , m , k;

int main()
{
    cin >> n >> m >> k;
    for(int i = 1 ; i <= n ; i++)
    {
        string s;
        cin >> s;
        for(int j = 1 ; j <= m ; j++)
            mp[i][j] = s[j - 1] - '0';
    }

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            for(int K = 0 ; K < (k + 1) ; K++)
                dp[i][j][K] = {-10000000 , ""};//初始化

    for(int j = 1 ; j <= m ; j++)
        dp[1][j][mp[1][j] % (k + 1)] = {mp[1][j] , ""};//初始化

    //从第一行走到最后一行 和 最后一行走到第一行 其实没有区别 为了方便输出起点
    //我们从最后一行走到第一行

    for(int i = 2 ; i <= n; i++)
        for(int j = 1 ; j <= m ; j++)
        {
            int L = j - 1 , R = j + 1;
            for(int K = 0 ; K < (k + 1) ; K++)//枚举上一行 余数为K
            {
                if(L >= 1)
                {
                    if(dp[i][j][(mp[i][j] + dp[i - 1][L][K].first) % (k + 1)].first 
                        < mp[i][j] + dp[i - 1][L][K].first )
                        dp[i][j][(mp[i][j] + dp[i - 1][L][K].first) % (k + 1)]
                         = {mp[i][j] + dp[i - 1][L][K].first , dp[i - 1][L][K].second + "L"};
                         //转移过来
                }
                if(R <= m)
                {
                    if(dp[i][j][(mp[i][j] + dp[i - 1][R][K].first) % (k + 1)].first 
                        < mp[i][j] + dp[i - 1][R][K].first )
                        dp[i][j][(mp[i][j] + dp[i - 1][R][K].first) % (k + 1)]
                         = {mp[i][j] + dp[i - 1][R][K].first , dp[i - 1][R][K].second + "R"};
                }
            }
        }
    int ans = -1 , begin ; string res = "";
    for(int i = 1 ; i <= m ; i++)
    {
        if(ans < dp[n][i][0].first)ans = dp[n][i][0].first , res = dp[n][i][0].second , begin = i;
    }
    if(ans == -1)cout << -1;
    else{
        cout << ans << endl;
        cout << begin << endl;
        for(int i = res.size() - 1 ; i >= 0 ; i--)cout << res[i];//倒着输出
    }



    return 0;
}