题目描述

blablabla

样例

blablabla

算法1

简单的dp

由于n,m,k数据小，故考虑dp

C++ 代码

#include<iostream>
#include<sstream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<vector>
#include<stack>
#include<iomanip>
#include<climits>

#define x first
#define y second

typedef long long LL;
typedef std::pair<long long,long long> PLL;
typedef std::pair<int,int>PII;
const int N = 110,M = 11,inf = 0x3f3f3f3f,mod = 1e9 + 7;
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};

int n,m,k;

std::string res[N][N][12];
void solve()
{  
   std::cin >> n >> m >> k;
   std::vector<std::vector<int>>mp(n + 1,std::vector<int>(m + 1));
  for(int i = 1; i <= n; i ++)
     for(int j = 1; j <= m; j ++)
      scanf("%1d",&mp[i][j]);
    std::vector<std::vector<std::vector<int>>> dp(n + 1,std::vector<std::vector<int>>(m + 1,std::vector<int>(12,-1e9)));

 for(int i = 1; i <= m; i ++)dp[n][i][mp[n][i] % (k + 1)] = mp[n][i];

      for(int i = n - 1; i >= 1; i --)
         for(int j = 1; j <= m; j ++)
         {
             for(int p = 0; p <= k; p ++)
             {
              if(j != m)
              {
                  if((dp[i + 1][j + 1][((p - mp[i][j]) % (k + 1) + (k + 1)) % (k + 1)] != -1e9) && (dp[i][j][p] < dp[i + 1][j + 1][((p - mp[i][j]) % (k + 1) + (k + 1)) % (k + 1)] + mp[i][j]))
                  {
                      dp[i][j][p] = dp[i + 1][j + 1][((p - mp[i][j]) % (k + 1) + (k + 1)) % (k + 1)] + mp[i][j];
                      res[i][j][p] = "";
                      res[i][j][p] += res[i + 1][j + 1][((p - mp[i][j]) % (k + 1) + (k + 1)) % (k + 1)];
                      res[i][j][p] += 'L';
                      //if(i == 1 && j == 3 && p == 0)std::cout << "右边来的" << std::endl;
                  }
                  //dp[i][j][p] = std::max(dp[i][j][p],dp[i + 1][j + 1][((p - mp[i + 1][j + 1]) % (k + 1) + (k + 1)) % (k + 1)] + mp[i][j]);
              }
              if(j != 1)
              {
                  if((dp[i + 1][j - 1][((p - mp[i][j]) % (k + 1) + (k + 1)) % (k + 1)] != -1e9) && (dp[i][j][p] < dp[i + 1][j - 1][((p - mp[i][j]) % (k + 1) + (k + 1)) % (k + 1)] + mp[i][j]))
                  {
                        dp[i][j][p] = dp[i + 1][j - 1][((p - mp[i][j]) % (k + 1) + (k + 1)) % (k + 1)] + mp[i][j];
                        res[i][j][p] = "";
                        res[i][j][p] += res[i + 1][j - 1][((p - mp[i][j]) % (k + 1) + (k + 1)) % (k + 1)];
                        res[i][j][p] += 'R';
                  }
              }
                  //dp[i][j][p] = std::max(dp[i][j][p],dp[i + 1][j - 1][((p - mp[i + 1][j - 1]) % (k + 1) + (k + 1))% (k + 1)] + mp[i][j]);
              }
              //dp[i][j][p] = std::max(dp[i + 1][j + 1][((p - mp[i + 1][j + 1]) % k + k) % k],dp[i + 1][j - 1][((p - mp[i + 1][j - 1]) % k + k) % k]) + mp[i][j];
            }
  int ans = -1,col = 0;
  std::string path = "";
  for(int i = 1; i <= m; i ++)
     if(ans < dp[1][i][0])
     {
        ans = dp[1][i][0];
        col = i;
        path = res[1][i][0];
     }
  if(ans >= 0)
  {
      std::cout << ans << std::endl;
      for(int i = 0; i < path.size(); i ++)
        if(path[i] == 'L')col ++;
         else col --;
      std::cout << col << std::endl;
      std::cout << path << std::endl;
  }
  else std::cout << -1 << std::endl;
} 
int main(void) 
{
    //std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
    int T = 1;
    //std::cin >> T;
    while(T --)
       solve();
    return 0;
}