题意思路: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)
好友链接
搜索
最新评论
阅读排行榜
评论排行榜
|
|