#576611 (C++17) No.1284 Flip Game

• 問題: No.1284 Flip Game
• ユーザー: 沙耶花
• 提出日時: 2020-11-06 22:05:51
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 40 ms / 2,000 ms
• コード長: 943 bytes
• コンパイル時間: 2,156 ms
• コンパイル使用メモリ: 212,876 KB
• 実行使用メモリ: 22,096 KB
• 最終ジャッジ日時: 2023-09-29 18:47:58
• 合計ジャッジ時間: 3,854 ms
• ジャッジサーバーID （参考情報）: judge12 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	23 ms; 21,856 KB
testcase_01	AC	24 ms; 21,916 KB
testcase_02	AC	24 ms; 21,892 KB
testcase_03	AC	24 ms; 21,840 KB
testcase_04	AC	25 ms; 21,900 KB
testcase_05	AC	24 ms; 21,836 KB
testcase_06	AC	26 ms; 21,828 KB
testcase_07	AC	23 ms; 21,964 KB
testcase_08	AC	24 ms; 21,896 KB
testcase_09	AC	24 ms; 22,092 KB
testcase_10	AC	24 ms; 21,840 KB
testcase_11	AC	24 ms; 21,828 KB
testcase_12	AC	24 ms; 21,832 KB
testcase_13	AC	24 ms; 21,808 KB
testcase_14	AC	25 ms; 21,900 KB
testcase_15	AC	25 ms; 21,828 KB
testcase_16	AC	25 ms; 21,828 KB
testcase_17	AC	28 ms; 21,964 KB
testcase_18	AC	27 ms; 21,860 KB
testcase_19	AC	37 ms; 21,828 KB
testcase_20	AC	26 ms; 21,920 KB
testcase_21	AC	29 ms; 22,096 KB
testcase_22	AC	29 ms; 21,832 KB
testcase_23	AC	36 ms; 21,812 KB
testcase_24	AC	40 ms; 21,896 KB
testcase_25	AC	38 ms; 21,836 KB
testcase_26	AC	37 ms; 21,920 KB
testcase_27	AC	37 ms; 21,844 KB

ソースコード

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 10000000000000000

vector<vector<long long>> c;
int N;
long long get(int A,int B,int last){
	if(A==(1<<N)-1)return 0;
	static vector dp(512,vector(512,vector(9,-1)));
	
	if(dp[A][B][last]!=-1)return dp[A][B][last];
	long long ret = Inf;
	rep(i,N){
		if((A>>i)&1)continue;
		long long temp = c[last][i];
		int nA = A|(1<<i);
		int nB = B;
		if((B>>last)&1){
		}
		else{
			nB |= 1<<last;
			nA ^= 1<<last;
		}
		ret = min(ret,temp + get(nA,nB,i));
	}
	
	dp[A][B][last] = ret;
	return ret;
}

int main(){
	
	
	cin>>N;
	
	c.resize(N,vector<long long>(N));
	rep(i,N){
		rep(j,N)cin>>c[i][j];
	}
	
	long long ans = Inf;
	
	rep(i,N){
		ans = min(ans,get(1<<i,0,i));

	}
	/*
	rep(i,1<<N){
		rep(j,1<<N){
			rep(k,N){
				cout<<get(i,j,k)<<',';
			}
			cout<<" ";
		}
		cout<<endl;
	}
	*/
	
	cout<<ans<<endl;
	
    return 0;
}