DFS #4 TLE 求调

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e2 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll n, m, siz, res, res2 = inf;
ll f[N];
unordered_map<ll, ll> dp1[N][N][15], dp[N][N][15];
ll dfs(int srt, int dep, int cho, ll lst, ll res)
{
  if (dp[srt][dep][cho].count(lst * 3 + res * 5))
    return dp[srt][dep][cho][lst * 3 + res * 5];
  if (cho == m && dep - srt == n - 1)
  {
    return dp[srt][dep][cho][lst * 3 + res * 5] = res * ((10 + lst % 10) % 10);
  }
  ll ans = 0;
  if (dep - srt < n)
  {
    if (cho < m)
      ans = max(ans, dfs(srt, dep + 1, cho + 1, f[dep], res * ((10 + lst % 10) % 10)));
    ans = max(ans, dfs(srt, dep + 1, cho, lst + f[dep], res));
  }
  return dp[srt][dep][cho][lst * 3 + res * 5] = ans;
}

ll dfs2(int srt, int dep, int cho, ll lst, ll res)
{
  if (dp1[srt][dep][cho].count(lst * 3 + res * 5))
    return dp1[srt][dep][cho][lst * 3 + res * 5];
  if (cho == m && dep - srt == n - 1)
  {
    return dp1[srt][dep][cho][lst * 3 + res * 5] = res * ((10 + lst % 10) % 10);
  }
  ll ans = inf;
  if (dep - srt < n)
  {
    if (cho < m)
      ans = min(ans, dfs2(srt, dep + 1, cho + 1, f[dep], res * ((10 + lst % 10) % 10)));
    ans = min(ans, dfs2(srt, dep + 1, cho, lst + f[dep], res));
  }

  return dp1[srt][dep][cho][lst * 3 + res * 5] = ans;
}

void solve()
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    cin >> f[i];
    f[i + n] = f[i];
  }
  for (int i = 1; i <= n; i++)
  {
    res = max(res, dfs(i + 1, i + 1, 1, f[i], 1));
    res2 = min(res2, dfs2(i + 1, i + 1, 1, f[i], 1));
  }
  cout << res2 << "\n"
       << res;
}
int main()
{

#ifdef LOCAL
  freopen("/Users/hukeren/Code/CppPrograms/洛谷/test/in.txt", "r", stdin);
  freopen("/Users/hukeren/Code/CppPrograms/洛谷/test/out.txt", "w", stdout);
#endif

  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  solve();

#ifdef LOCAL
  fclose(stdin);
  fclose(stdout);
#endif

  return 0;
}