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

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的启发，提一点对于奇数项数数列甲乙二人的取数策略，抛砖引玉，大家讨论一下。

定义：当数列项数为偶数时，奇数项之和与偶数项之和差值的绝对值设为该数列的“益差”，如果“益差”为正，设较大的和为该数列的收益，先取数的人可以通过只取奇（或偶）数项来获得这个收益。

奇数项数数列，甲先取，甲的策略如下：将甲取到的值减去剩下数列的“益差”，记为Aa（可以为负），取Aa大的一边来取，如果两边Aa相等，可以取前后两项中较大的数，如果这种情况下前后两项还相等，那就任意选一边。

甲取完之后乙的策略：乙面对的是偶数项数数列，初始的时候可以设定收益期望为该数列的收益Ab，这时该选哪一边的数也确定了（注意这个数只跟奇偶项有关，不一定较大），设这个数为b，然后其收益期望调整为Ab-b。之后轮到甲取数，双方的策略没有耦合关系，甲取完后，又轮到乙取数了，乙这个时候要重新评估一下剩下的偶数项数数列，如果发现其收益大于Ab-b，则重置取数策略，否则继续按原来的奇数项或偶数项来取。

[ 本帖最后由 金眼睛 于 2009-4-4 14:00 编辑 ]

lulijie

哈哈，6楼的 f( i, j ) 表示  从数列第i个数到第j个数的排列，双方最优取法下 S先 的值。
而我的 f( i, j ) 表示从数列第i个数到第j个数的排列，双方最优取法下 S先-S后的值。
-------------------------------------------------------------------------------------------------------
定义不同，所以递推公式也不同。
我的递推公式也是正确的。
用我自己的递推公式已经算出yang_bigarm的贴 两头取数的问题 中举的例子的双方最优的取法。
已公布在两头取数的问题 的贴中，大家验证一下我解出的答案对不对。

zxl0714

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

lulijie

很对，楼上的定义：     f( i, j ) = max{ sum( i, j ) - f( i + 1, j ), sum( i, j ) - f( i, j - 1 ) }
               可化简为    f( i, j )=sum( i, j ) -  min{ f( i + 1, j ), f( i, j - 1 ) }
          应该更简单些。

zxl0714

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

lulijie

但是我用两种方法都试了一下，解    47 30 1 47 2 30 45 7 37 82 9 97 48 32 78 92 74 83
我的方法 3秒，
你的方法 4秒。
好像你的方法并不比我的快啊。

Cielo

原帖由 lulijie 于 2009-4-4 21:11 发表
但是我用两种方法都试了一下，解    47 30 1 47 2 30 45 7 37 82 9 97 48 32 78 92 74 83
我的方法 3秒，
你的方法 4秒。
好像你的方法并不比我的快啊。

呵呵都是强人，佩服！

zxl0714

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