USACO Section 3.3: A Game

ゲーム理論の問題に初めて出会ったのは、とても厄介で、ゲーム理論の問題は全局の最良の解法を考慮しなければならなくて、私は初めて局部の最良を使って、その上vectorもpop_がありませんfront()操作.後でネット上のdpの方法で解いたのを見ました.
ゲーム理論のテーマは基本的にdp法を使わなければならない.最も簡単な状況から上へ推定しなければならないからだ.

 1 /*

 2 ID: yingzho1

 3 LANG: C++

 4 TASK: game1

 5 */

 6 #include <iostream>

 7 #include <fstream>

 8 #include <string>

 9 #include <map>

10 #include <vector>

11 #include <set>

12 #include <algorithm>

13 #include <stdio.h>

14 #include <queue>

15 #include <cstring>

16 #include <cmath>

17 #include <list>

18 #include <cstdio>

19 #include <cstdlib>

20 #include <limits>

21 #include <stack>

22 

23 using namespace std;

24 

25 ifstream fin("game1.in");

26 ofstream fout("game1.out");

27 

28 int N;

29 

30 int main()

31 {

32     fin >> N;

33     vector<int> board(N);

34     int total = 0;

35     vector<vector<int> > score(N, vector<int>(N)), sum(N, vector<int>(N));

36     for (int i = 0; i < N; i++) {

37         fin >> board[i];

38         total += board[i];

39         sum[i][i] = score[i][i] = board[i];

40     }

41     for (int i = 0; i < N; i++) {

42         for (int j = i+1; j < N; j++) {

43             sum[i][j] = sum[i][j-1] + board[j];

44         }

45     }

46     for (int l = 1; l < N; l++) {

47         for (int i = 0; i < N-l; i++) {

48             score[i][i+l] = sum[i][i+l] - min(score[i][i+l-1], score[i+1][i+l]);

49         }

50     }

51     fout << score[0][N-1] << " " << total - score[0][N-1] << endl;

52 

53     return 0;

54 }