程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ 2576 Tug of War

POJ 2576 Tug of War

編輯:關於C++

剛開始一直在糾結怎麼記錄人數,因為一開始的想法是dp[i][j]表示前i個人是否能達j這個值,想過用狀態壓縮存儲路徑,然後發現狀態壓縮只適合在人數<20時,時間和空間復雜度才可以接受,也想過用數組存儲人數,但也不好操作,看了別人的解題報告,才發現自己想太多了,這裡根本不需要知道路徑,只需要知道到達j這個值時,有多少個人就可以了。所以直接加一個狀態表示人數,於是狀態就變成了:dp[i][k][j]表示前i 個人時,選k個人時,是否能到達j值

然後考慮到空間復雜度,省略i這個狀態,用逆序保證每個人只選一次

 

#include 
#include
int dp[105][45005],w[105];
int n;
void init(){
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif
	scanf("%d",&n);
	int sum=0;
	for(int i=1;i<=n;i++) {
		scanf("%d",&w[i]);
		sum+=w[i];
	}
	init();
	for(int i=1;i<=n;i++){
		for(int j=sum;j-w[i]>=0;j--){
			for(int k=n/2+1;k>=1;k--){
				if(dp[k-1][j-w[i]]) {
					dp[k][j]=dp[k-1][j-w[i]];
				}
			}
		}
	}
	for(int i=sum/2;i>=0;i--){
		if(n&1) {
			if(dp[n/2][i]||dp[n/2+1][i]) {
				printf("%d %d\n",i,sum-i);
				break;
			}
		}
		else{
			if(dp[n/2][i]) {
				printf("%d %d\n",i,sum-i);
				break;
			}
		}
	}
	return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved