首页 > 代码库 > UVA 10891 Game of Sum
UVA 10891 Game of Sum
题解:
这个题的题意挺误解人的。
每次选取的最优策略。我的理解每次从左开始。或从右开始。选取最大值(每个位置选取的最大值的位置是固定的).把剩下的序列给对方....但题意并不是这样
看了题解。
表示dp[ i ][ j ] 表示 区间 i j 先选得到的最大值.
dp[ i ][ j ] = sum( j ) - sum( i - 1 ) - min( dp( i + 1, j ), dp( i + 2, j ), dp( i + 3, j )...dp( j ,j ), dp( i , j - 1 ), dp( i ,j - 2 ).....dp( i ,i ), 0 );
o( n ^ 3 ) 和o( n ^ 2 )的优化书上写得很清楚了,不多说
代码:
#include<bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define se second #define fs first #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define pii pair<int,int> const int INF = 1000000000; const int maxn = 105; int n; int a[ maxn ], sum[ maxn ]; int dp[ maxn ][ maxn ], vis[ maxn ][ maxn ]; int DP( int l, int r ) { if( vis[ l ][ r ] ) return dp[ l ][ r ]; vis[ l ][ r ] = 1; int m = 0; for( int i = l + 1; i <= r; i ++ ) m = min( m, DP( i, r ) ); for( int i = r - 1; i >= l; i -- ) m = min( m, DP( l ,i ) ); return dp[ l ][ r ] = sum[ r ] - sum[ l - 1 ] - m; } int main() { while( ~scanf( "%d", &n ) && n ) { for( int i = 1; i <= n; i ++ ) { scanf( "%d", &a[ i ] ); sum[ i ] = sum[ i - 1 ] + a[ i ]; } memset( vis, 0, sizeof( vis ) ); printf( "%d\n", DP( 1 , n ) * 2 - sum[ n ] ); } return 0; }
#include<bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define se second #define fs first #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define pii pair<int,int> const int INF = 1000000000; const int maxn = 105; int n; int a[ maxn ], sum[ maxn ]; int dp[ maxn ][ maxn ], f[ maxn ][ maxn ], g[ maxn ][ maxn ]; int main() { while( ~scanf( "%d", &n ) && n ) { for( int i = 1; i <= n; i ++ ) { scanf( "%d", &a[ i ] ); sum[ i ] = sum[ i - 1 ] + a[ i ]; } for( int i = 1; i <= n; i ++ ) f[ i ][ i ] = g[ i ][ i ] = dp[ i ][ i ] = a[ i ]; for( int k = 1; k < n; k ++ ) for( int i = 1; i + k <= n; i ++ ) { int j = i + k; int m = 0; m = min( m, f[ i + 1 ][ j ] ); m = min( m, g[ i ][ j - 1 ] ); dp[ i ][ j ] = sum[ j ] - sum[ i - 1 ] - m; f[ i ][ j ] = min( f[ i + 1 ][ j ], dp[ i ][ j ] ); g[ i ][ j ] = min( g[ i ][ j - 1 ], dp[ i ][ j ] ); } printf( "%d\n", 2 * dp[ 1 ][ n ] - sum[ n ] ); } return 0; }
UVA 10891 Game of Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。