AOJ 2517 : Hotel - 土下座しながら探索中

解法：
動的計画法を行う
D日間にかかるホテルの費用の最小は各日にちでもっとも安いホテルを選んだときの費用の和だが、
移動回数の最小化や複数あったときに辞書順で最小のものを選びたいのでDPする

配列は
dp[何日目][ホテル][ホテルを移動した回数] := 最小の費用　とした
これと同様に、
path[何日目][ホテル][ホテルを移動した回数] := １つ前に訪れたホテルで番号が最小のもの
という配列を経路復元のために用意する

dp自体は特に工夫する点はない
dpで最小費用と経路を配列に記録したあとに復元を行う
ここで、経路は普通一番最後から(D日目から)行うと思うが
そのまま後ろから復元して行くと辞書順最小にならない
D日からさかのぼってみれば辞書順最小になっているが、
それをリバースするわけだから正しくはならない
というわけでホテルの日にちごとの入力をリバースする
つまり、あるホテルの３日間の費用が
1 2 3　だとすると、これを
3 2 1　にする
こうする亊で辞書順最小にできる

コーナーケース
Sample 1:
Input :
2 1
1 2
1 1

Output:
2 0
2
2

Sample 2:
Input :
2 1
2 1
1 1
Output :
2 0
2
2

Sample 3:
Input :
5 10
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 1 1 1
Output:
10 0
5
5
5
5
5
5
5
5
5
5

コード :

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define inf (1<<29)
#define MAX 100
using namespace std;
typedef long long ll;

/*
経路復元用
dp[day][hotel][number] := minimum
 */
int dp[MAX][MAX][MAX];
int path[MAX][MAX][MAX];
int N,D,p[MAX][MAX];

int main()
{
  scanf("%d %d",&N,&D);
  rep(i,N)
    {
      rep(j,D)scanf("%d",&p[i][j]);
      reverse(p[i],p[i]+D);
    }
  
  rep(i,D+1)rep(j,N)rep(k,55)
    {
      dp[i][j][k] = inf;
      path[i][j][k] = inf;
    }

  rep(i,N)dp[0][i][0] = 0;

  rep(day,D)
    {
      rep(hotel,N)
	{
	  rep(number,55)
	    {
	      if(dp[day][hotel][number] == inf)continue;
	      rep(next_hotel,N)
		{
		  int add = (hotel != next_hotel);
		  if(dp[day+1][next_hotel][number+add] > dp[day][hotel][number]+p[next_hotel][day])
		    {
		      dp[day+1][next_hotel][number+add] = dp[day][hotel][number]+p[next_hotel][day];
		      path[day+1][next_hotel][number+add] = hotel;
		    }
		  else if(dp[day+1][next_hotel][number+add] == dp[day][hotel][number]+p[next_hotel][day])
		    {
		      if(path[day+1][next_hotel][number+add] > hotel)path[day+1][next_hotel][number+add] = hotel;
		    }
		}
	    }
	}
    }

  int mincost,minnumber,minN;
  mincost = minnumber = minN = inf;

  rep(i,N)rep(j,55)
    {
      if(mincost >= dp[D][i][j])
	{
	  if(mincost == dp[D][i][j])
	    {
	      if(minnumber >= j)
		{
		  if(minnumber == j)
		    {
		      if(minN > i)
			minN = i;
		    }
		  else
		    {
		      minnumber = j;
		      minN = i;
		    }
		}
	    }
	  else
	    {
	      mincost = dp[D][i][j];
	      minnumber = j;
	      minN = i;
	    }
	}
    }

  cout << mincost << " " << minnumber << endl;
  vector<int> ph;
  int d,h,n;

  d = D,h = minN, n = minnumber;

  int diff = p[h][D-1];
  for(;d >= 0 && n >= 0;)
    {
      ph.push_back(h);

      int next_h = path[d][h][n];
      int next_n = n - (next_h != h);
      h = next_h;
      n = next_n;
      d--;
      diff += p[h][d-1];
      if(path[d][h][n] == inf)break;
    }
  rep(i,ph.size())
    {
      cout << ph[i]+1 << endl;
      assert(ph[i]!=inf);
    }
  return 0;
}