対数

17158 ワード
対数 boj 2494 acmicpc テキストリンク
Problem link: https://www.acmicpc.net/problem/2494
13392題--방법을 출력하지 않는 숫자 맞추기題にbacktrackingを追加すればよい.
詳細な解答は13392題の解答を参照してください.
それでも何も書かないのは気まずいので、次のような解答を書きましょう.
トップダウンDPを利用すれば、以下のようにCACHEを定義できます.
  • CACHE[i][j]:i-1|は、番号付けネジまで揃えられており、これまで使用していた左折数がjの場合、残りの番号付けネジ(i ~ N)に必要な最小移動回数
    • CACHE[i][j]の場合、jを使用して、現在のi番号付けネジの状態を知ることができます.i号ネジを左折した場合、それを右折に分割した場合、再帰呼び出しでDPを行います.
    完了したDPテーブルを使用してバックグラウンド追跡を行います.DPテーブルの構成と同様です.
    #include <cstdio>
#include <algorithm>

using namespace std;

const int kMaxN = 10000;
const int kNumOfDigits = 10;

int SRC[kMaxN + 1];
int DST[kMaxN + 1];

int N;
int CACHE[kMaxN + 1][kNumOfDigits];

void Initialize()
{
  for (int i = 0; i < kMaxN + 1; ++i)
  {
    for (int j = 0; j < kNumOfDigits; ++j)
    {
      CACHE[i][j] = -1;
    }
  }
}

int Solve(const int screw_idx, const int left_turn)
{
  if (screw_idx > N)
  {
    return 0;
  }

  int& ret = CACHE[screw_idx][left_turn];
  if (ret != -1)
  {
    return ret;
  }

  int current = (SRC[screw_idx] + left_turn) % kNumOfDigits;
  int target = DST[screw_idx];

  int lmove = ((target - current) + kNumOfDigits) % kNumOfDigits;
  int rmove = ((current - target) + kNumOfDigits) % kNumOfDigits;

  ret = min(lmove + Solve(screw_idx + 1, (left_turn + lmove) % kNumOfDigits), rmove + Solve(screw_idx + 1, left_turn));

  return ret;
}

void Backtrack(const int screw_idx, const int left_turn)
{
  if (screw_idx > N)
  {
    return;
  }

  int current = (SRC[screw_idx] + left_turn) % kNumOfDigits;
  int target = DST[screw_idx];

  int lmove = ((target - current) + kNumOfDigits) % kNumOfDigits;
  int rmove = ((current - target) + kNumOfDigits) % kNumOfDigits;

  int left_chosen = lmove + Solve(screw_idx + 1, (left_turn + lmove) % kNumOfDigits);
  int right_chosen = rmove + Solve(screw_idx + 1, left_turn);

  if (left_chosen < right_chosen)
  {
    printf("%d %d\n", screw_idx, lmove);
    Backtrack(screw_idx + 1, (left_turn + lmove) % kNumOfDigits);
  }
  else
  {
    printf("%d %d\n", screw_idx, -rmove);
    Backtrack(screw_idx + 1, left_turn);
  }

  return;
}

int main(void)
{
  // Read Inputs
  scanf(" %d", &N);
  for (int i = 1; i <= N; ++i)
  {
    scanf(" %1d", &SRC[i]);
  }
  for (int i = 1; i <= N; ++i)
  {
    scanf(" %1d", &DST[i]);
  }

  // Initialize
  Initialize();

  // Print total movements
  printf("%d\n", Solve(1, 0));

  // Print backtracking
  Backtrack(1, 0);

  return 0;
}
    リバースリンクリスト
    有向非巡回グラフ(DAG)におけるトポロジカルソーティング