2020-01-19 13:52:29 C++

C++

Copy Copied! Full
#include <iostream> #include <vector> #include <algorithm> using namespace std; const int INF = 1145141919; int color(int init, int pos) { if (init < pos)swap(init, pos); return (init - pos) % 2; } int main() { int n; cin >> n; vector<vector<int>> card(n, vector<int>(2)); for (int i = 0; i < n; i++)cin >> card[i][0]; for (int i = 0; i < n; i++)cin >> card[i][1]; vector<vector<int>> dp(1 << n, vector<int>(n, INF)); dp[0][0] = 0; //dp[i][j] := 状態をiにして 最後にjを追加してる? for (int nowBit = 0; nowBit < 1 << n; nowBit++) { int bitCount = 0; for (int i = 0; i < n; i++) { //もしもiビット目に1が立っていたらbitCountを++する; if (nowBit & (1 << i))bitCount++; } if (nowBit == 0) { //もしも全てのbitが0だったら dp[ 1<< next ][next] = 0 + next; //多分nextは添字 添字のnext番目を状態に追加してる? next番目だけを1にして、dp[1<<next][next] = next; //ここのnextってのが、最後に追加した数の添字? for (int next = 0; next < n; next++) dp[1 << next][next] = dp[0][0] + next; } else { //nowBitが1以上の場合だから どこかのbitは必ず数字が立っている for (int prev = 0; prev < n; prev++) { if ((nowBit & (1 << prev)) == 0)continue; //nowBit の prev番目のbitが立っていなかったら次に進む //もしもprev番目のbitが立っていたら int notused = 0; for (int next = 0; next < n; next++) { //nextは次に追加するカードのindex if (nowBit & (1 << next))continue; //もしも現在のbitにすでにnext番目の数が追加されていたらcontinue; //追加されていなかったらnext番目のカードを集合に入れる int prevnum = card[prev][color(prev, (bitCount - 1) % 2)]; int nextnum = card[next][color(next, bitCount % 2)]; if (prevnum <= nextnum) { int nextBit = nowBit | (1 << next); dp[nextBit][next] = min(dp[nextBit][next], dp[nowBit][prev] + notused); } notused++; } } } } int ret = INF; for (auto x:dp[(1 << n) - 1])ret = min(ret, x); cout << (ret == INF ? -1 : ret) << endl; return 0; }
RECOMMEND