ProjectEuler Problem345 : Matrix Sum

問題リンク：Problem 345 - Project Euler

問題概要：
問題で与えられる15*15の2次配列から行も列もかぶらないように数字を選んでいく
１５個全て選んだときの最大値をもとめろ

解法：
選んだ状態での最大値を保存してdfsで探索した
dp[1<<16]という配列を用意し、そのbitの状態での最大値を保存する
dfs(x,y,visited,cost)とし,visitedはそれまでに使った場所にビットをたてたものとした
ひょっとしたら嘘解法？

コード：

#include<iostream>
#include<algorithm>

using namespace std;

int list[16][16] =
  {
    {  7, 53,183,439,863,497,383,563, 79,973,287, 63,343,169,583},
    {627,343,773,959,943,767,473,103,699,303,957,703,583,639,913},
    {447,283,463, 29, 23,487,463,993,119,883,327,493,423,159,743},
    {217,623,  3,399,853,407,103,983, 89,463,290,516,212,462,350},
    {960,376,682,962,300,780,486,502,912,800,250,346,172,812,350},
    {870,456,192,162,593,473,915, 45,989,873,823,965,425,329,803},
    {973,965,905,919,133,673,665,235,509,613,673,815,165,992,326},
    {322,148,972,962,286,255,941,541,265,323,925,281,601, 95,973},
    {445,721, 11,525,473, 65,511,164,138,672, 18,428,154,448,848},
    {414,456,310,312,798,104,566,520,302,248,694,976,430,392,198},
    {184,829,373,181,631,101,969,613,840,740,778,458,284,760,390},
    {821,461,843,513, 17,901,711,993,293,157,274, 94,192,156,574},
    { 34,124,  4,878,450,476,712,914,838,669,875,299,823,329,699},
    {815,559,813,459,522,788,168,586,966,232,308,833,251,631,107},
    {813,883,451,509,615, 77,281,613,459,205,380,274,302, 35,805}
  };
int mex;
int dp[1<<16];
void dfs(int x,int y,int visited,int cost)
{
  if(y >= 15)
    {
      mex = max(mex,cost);
      return;
    }
  if(dp[visited] >= cost)
    return;
  dp[visited] = cost;

  for(int i=0;i<15;i++)
    {
      if((visited>>i) & 1)
	continue;
      dfs(i,y+1,visited|(1<<i),cost+list[i][y]);
    }

}

int main()
{
  for(int i=0;i<(1<<16);i++)
    dp[i] = 0;
  mex = 0;
  for(int i=0;i<15;i++)
    {
      dfs(i,1,(1<<i),list[i][0]);
    }
  cout << mex << endl;
  return 0;
}