読者です 読者をやめる 読者になる 読者になる

UVa115533 GRID GAME

問題
http://uva.onlinejudge.org/external/115/11553.html

解法
Bobが最善の手を取ってきた前提でAliceの得点を最大化する。

#include <iostream>
#include <algorithm>
#include <limits>
using namespace std;

int main() {
  
  int grid[8][8];
  int Tc; cin >> Tc;
  while(Tc--) {
    int N; cin >> N;
    for(int i=0; i<N; i++)
      for(int j=0; j<N; j++) cin >> grid[i][j];
    
    int per[N]; iota(per, per+N, 0);
    
    int alice = numeric_limits<int>::min();
    int bob   = numeric_limits<int>::min();
    do {
      int num = 0;
      for(int i=0; i<N; i++) {
        num -= grid[i][per[i]];
      }
      if(num > bob) {
        bob = num;
        alice = -num;
      } else if(num == bob) {
        if(alice < -num) alice = -num;
      }
    } while(next_permutation(per, per+N));
    
    cout << alice << endl;
  }
  
  return 0;
}