TOJ 2378

テーマ接続:
http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=2378
テーマのタイプ:
ダイナミック企画-01リュックサック
データ構造:

//       
int dp[25005][105];

考え方の分析:
-------------------------------------------
本題の原意は等分問題で、
すべての人を2つのチームに分けて、1チームの人数の差が1を超えてはいけないことを求めて、体重の差が最小であることを求めます。
それを01リュックに変換し、
人数の差が1より大きくならないなら、人数を2で割って、人数が奇数なら、1を加えて2で割る。
半分の人数を得る
同じ理屈で、すべての体重の和を2で割る。
全体の重さを半分にしました。
問題はn人（またはn-1人の総人数が奇数の場合）に変換されます。
体重はなるべくmに近いです
一チームになると体重ができるだけ近づいてくるからです。
その反対もどんどん近づいてきます。
ですから、二次元のリュックサックの問題が発生すればいいです。
最終的な答えdp[m][n](またはdp[m]、[n-1])どちらがmに近いかが答えです。
証明:
ソースコード:

#include 
#include 
using namespace std;

//       
int dp[25005][105];

int _abs( int a )
{
	return a < 0 ? -1 * a : a;
}

int main()
{
	int i, j, k, n, m, l;
	int arr[105];
	
	while( scanf( "%d", &n ) != EOF )
	{
		for (i = 0; i <= 25001; i++)
		{
			for (j = 0; j <= 101; j++)
			{
				if( j )
				{
					dp[i][j] = -999999;
				}
				else
				{
					dp[i][j] = 0;
				}
			}
		}
		
		int snt = 0;
		
		for( i = 1; i <= n; i ++ )
		{
			scanf( "%d", &arr[i] );
			snt += arr[i];
		}
		
		l = snt % 2 == 0 ? snt / 2 : ( snt + 1 ) / 2;
		m = n % 2 == 0 ? n / 2 : ( n + 1 ) / 2;
	
		for( i = 1; i <= n; i ++ )
		{
			for( j = l; j >= arr[i]; j -- )
			{
				for( k = m; k >= 1; k -- )
				{
					if( dp[j][k] < dp[j - arr[i]][k - 1] + arr[i] )
					{
						dp[j][k] = dp[j - arr[i]][k - 1] + arr[i];
					}
				}
			}
		}
		
		int rlt = _abs( snt - 2 * dp[l][m] ) < _abs( snt - 2 * dp[l][m - 1] ) ? dp[l][m] : dp[l][m - 1];
		
		if( rlt <= 0 )
		{
			printf( "%d %d
", 0, snt );
		}
		else
		{
			if( rlt > snt - rlt )
			{
				printf( "%d %d
", snt - rlt, rlt );
			}
			else
			{
				printf( "%d %d
", rlt, snt - rlt );
			}
		}
	}
	
	return 0;
}