探讨“ 两头取数的问题” 的程序设计思路

zxl0714

算法设计起来并不难，这道题应该是用动态规划。用f( i, j )来表示第i个数到第j个数的先拿的人能拿到的最大值，这样有状态转移方程f( i, j ) = max{ sum( i, j ) - f( i + 1, j ), sum( i, j ) - f( i, j - 1 ) }，sum( i, j )表示第i个数到第j个数的和，这样就可以递推了。

zxl0714

如果n是偶数，谁先手谁肯定不会输，因为先手的人必然可以取得所有奇数位置上的数或者偶数位置上的数。当n是奇数的时候就没那么简单了。

zxl0714

楼上的递推公式显然错了。
首先当i等于j的时候f( i, j )可以确定，可以从这里出发，自底向上，也可以用递归自顶向下。

zxl0714

楼上那个数列，举几个例子。
f( 1, 1 ) = 47，f( 2, 2 ) = 30，f( 3, 3 ) = 1，因为只有一个数先拿者必拿到这么多。
f( 1, 2 ) = max{ 47 + 30 - f( 1, 1 ), 47 + 30 - f( 2, 2 ) } = 47
f( 2, 3 ) = max{ 30 + 1 - f( 2, 2 ), 30 + 1 - f( 3, 3 ) } = 30
f( 1, 3  ) = max{ 47 + 30 + 1 - f( 1, 2 ), 47 + 30 + 1 - f( 2, 3 ) } = 48
这样一直推到f( 1, n )就是先拿的人在双方不出错的情况下所能拿到的最大数值。

zxl0714

1. #include <cstdio>
   
2. 
   
3. int min( int a, int b ) { return ( a < b )? a: b; }
   
4. 
   
5. int main( )
   
6. {
   
7.         int a[ 101 ], f[ 101 ][ 101 ], n, i, j, sum[ 101 ];
   
8.         scanf("%d", &n);
   
9.         for ( i = 1; i <= n; i++ )
   
10.                 scanf("%d", &f[ i ][ i ]);
    
11.         sum[ 0 ] = 0;
    
12.         for ( i = 1; i <= n; i++ )
    
13.                 sum[ i ] = sum[ i - 1 ] + f[ i ][ i ];
    
14.         for ( i = 1; i < n; i++ )
    
15.                 for ( j = 1; j + i <= n; j++ )
    
16.                         f[ j ][ i + j ] = sum[ i + j ] - sum[ j - 1 ] - min( f[ j + 1 ][ i + j ], f[ j ][ i + j - 1 ] );
    
17.         printf("%d\n", f[ 1 ][ n ]);
    
18.         return 0;
    
19. }

复制代码

程序写起来很简单

zxl0714

你解的答案是对的，你的状态和我的状态定义不同是我看漏了，不过我不得不说你这个状态的定义有点复杂了。

zxl0714

是的，我的程序就是这么写的

zxl0714

同是O(n^2)的算法，可以算一样长，但是为什么你这个计算的这么慢，这组数据n=18，我敢说肯定0,01秒内就能出解。

zxl0714

看来你还没有理解啊。。。。。
动态规划的主要思想就是避免重复计算，你可以这么想，为了确定第1步我们要计算出所有的来比较，第2步我们就不用再计算了，因为第1步已经计算过了。

zxl0714

我贴个伪码

1. input n
   
2. sum( 0 ) := 0
   
3. for i := 1 to n
   
4. begin
   
5.         input a( i )
   
6.         f( i, i ) := a( i )
   
7.         sum( i ) := sum( i - 1 ) + a( i )
   
8. end
   
9. for i := 1 to n
   
10.         for j := 1 to n
    
11.                 f( j, i + j ) = sum( i + j ) - sum( j - 1 ) - min( f( j + 1, i + j ), f( j, i + j - 1 ) )
    
12. print f( 1, n ), sum( n ) - f( 1, n )        //f( 1, n )是S甲，sum( n ) - f( 1, n )是S乙
    
13. 
    
14. //下面开始输出每个数第几次被取走
    
15. start := 1
    
16. end := n
    
17. for i := 1 to n
    
18. begin
    
19.         if f( start + 1, end ) < f( start, end - 1 )
    
20.         begin
    
21.                 p( start ) := i
    
22.                 start := start + 1
    
23.         end
    
24.         else
    
25.         begin
    
26.                 p( end ) := i
    
27.                 end := end - 1
    
28.         end
    
29. end
    
30. for i := 1 to n
    
31.         print p( i )

复制代码