題意思路:DP.這題一開始認為是dp，無奈不會表示狀態,于是一度認為是個博弈題(不知算不算博弈- -),上網一頓狂搜博弈,搜了好久也沒發現這題的簡化版之類的，不懂博弈的表示壓力很大~~。后來突然想到了一個比較笨的辦法,就是用兩個函數在那調來調去。也就是一個遞歸(發現一個函數也可以- -!)。寫出來一交TLE在第4組。又加了個記憶化，終于過了。每組數據的時間都在0.1S左右。 標稱的三種方法都很簡短,第一種還好想,后面兩種就比較難想了。 下面是標程的三種方法， 哪位牛人給說下第二種的best[i][j]表示什么以及轉移方程怎么來的(不是很懂),我表示感激不盡.
  標程
1 We use dynamic programming to determine, for every possible piece of board that could be left at any point in the game, how many points the best strategy gets for the winner, and how many for the loser.
2
3Let us define best[board] to be the highest score we can hope to get by going first starting with the given board.
4
5If we are looking at a board "a  b", the best number of points is the maximum of the following:
6 a + total[ b] - best[ b]
7 b + total[a ] - best[a ]
8
9
10We use total[board] - best[board] as the best that we can hope to do going second starting with the given board.
11
12If we are looking at the board "a", the best number of points is a.
13
14#include <stdio.h>
15#include <stdlib.h>
16#include <string.h>
17#include <assert.h>
18
19#define MAXBOARD 100
20
21int board[MAXBOARD];
22
23/**//*
24 * best and total are indexed so that (e.g.) best[i, l] refers
25 * to the board of length l starting at place i.
26 */
27int total[MAXBOARD][MAXBOARD];
28int best[MAXBOARD][MAXBOARD];
29
30int
31max(int a, int b)
32{
33 return a > b ? a : b;
34}
35
36void
37main(void)
38{
39 FILE *fin, *fout;
40 int j, l, n;
41
42 fin = fopen("game1.in", "r");
43 fout = fopen("game1.out", "w");
44 assert(fin != NULL && fout != NULL);
45
46 fscanf(fin, "%d", &n);
47 for(j=0; j<n; j++)
48 fscanf(fin, "%d", &board[j]);
49
50  /**//* calculate subboard totals */
51 for(j=0; j<n; j++)
52 total[j][0] = 0;
53
54 for(l=1; l<=n; l++)
55 for(j=0; j+l<=n; j++)
56 total[j][l] = board[j] + total[j+1][l-1];
57
58 /**//* calc best for boards of size one */
59 for(j=0; j+1<=n; j++)
60 best[j][1] = board[j];
61
62 /**//* calc best for bigger boards */
63 for(l=2; l<=n; l++)
64 for(j=0; j+l<=n; j++)
65 best[j][l] = max(board[j] + total[j+1][l-1] - best[j+1][l-1],
66 board[j+l-1] + total[j ][l-1] - best[j ][l-1]);
67
68 fprintf(fout, "%d %d\n", best[0][n], total[0][n]-best[0][n]);
69
70 exit(0);
71}
72
73Another take on game1
74Nick Pilkington of South Africa writes:
75You only need O(n) space for the sum not O(n*n). This eliminates extra calculation as it can be computed during input. This also means that the board values don't need to be stored at all, leading to a much tighter solution:
76
77#include <fstream>
78
79using namespace std;
80
81#define min(a,b) ((a<b)?a:b)
82
83ifstream fin("game1.in");
84ofstream fou("game1.out");
85
86int n;
87int sum[101];
88int best[101][101];
89
90void main()
91{
92 fin >> n;
93 for(int i = 1; i <= n; i++) {
94 fin >> best[i][i];
95 sum[i] = sum[i-1] + best[i][i];
96 }
97
98 for(int i = 1; i <= n; i++)
99 for(int j = 1; j+i <= n; j++)
100 best[j+i][j] = sum[j+i]-sum[j-1] - min(best[j+i-1][j], best[j+i][j+1]);
101 fou << best[n][1] << " " << sum[n] - best[n][1] << endl;
102}
103
104More optimizations
105Lucian Boca Romania writes:
106I propose some memory optimizations for "A Game" problem.
107
108The algorithm is the same, I simulate the calculation of the matrix best[i][l] = the best score wich can be obtained by the first player with the board pieces i,i+1,,i+l-1 (a sequence of numbers starting with position i and having the length l). I also simulate the calculation of the matrix total[i][l] = the sum of all elements in the sequence starting with position i and having the length l. The reccurence relation is:
109
110best[i][l]=total[i][l] - min( best[i+1][l-1], best[i][l-1] )
111
112and our goal is to obtain best[1][n]
113The optimizations:
114
115You don't need to memorize the board. All the information about the board is in total(i,l)
116You don't need to use a matrix for total(i,l). You calculate a vector t[i]=the sum of elements 1,2,,i. So, total(i,l) will be t[i+l-1] - t[i-1]
117You don't need to use a matrix NxN, since you only need the last two columns. So, instead of using l, we can use l%2 and allocate the matrix best[NMAX][2]; the reccurence relation becomes best[i][l%2]=total(i,l) - min( best[i+1][(l-1)%2], best[i][(l-1)%2]) and our goal is to obtain best[1][n%2].
118Here's the code:
119#include <stdio.h>
120#define NMAX 101
121
122int best[NMAX][2], t[NMAX];
123int n;
124
125void
126readx () {
127 int i, aux;
128
129 freopen ("game1.in", "r", stdin);
130 scanf ("%d", &n);
131 for (i = 1; i <= n; i++) {
132 scanf ("%d", &aux);
133 t[i] = t[i - 1] + aux;
134 }
135 fclose (stdin);
136}
137
138inline int
139min (int x, int y) {
140 return x > y ? y : x;
141}
142
143void
144solve () {
145 int i, l;
146
147 for (l = 1; l <= n; l++)
148 for (i = 1; i + l <= n + 1; i++)
149 best[i][l%2] = t[i + l - 1] - t[i - 1] - min (best[i + 1][(l - 1) % 2],
150 best[i][(l - 1) % 2]);
151}
152
153void writex () {
154 freopen ("game1.out", "w", stdout);
155 printf ("%d %d\n", best[1][n % 2], t[n] - best[1][n % 2]);
156 fclose (stdout);
157}
158
159int
160main () {
161 readx ();
162 solve ();
163 writex ();
164 return 0;
165}
166
167
|
|
常用鏈接
留言簿(1)
隨筆分類(99)
隨筆檔案(71)
好友鏈接
搜索
最新評論
閱讀排行榜
評論排行榜
|
|