首页 > 代码库 > ZOJ - 1880 Tug of War
ZOJ - 1880 Tug of War
题意:求在两边人数不相差超过1个的情况下,实力尽量相等的情况
思路:从实力和的一半开始类背包操作
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 45010; const int MAXM = 110; int a[MAXM]; int dp[MAXN][MAXM]; int n; int main(){ int t,flag = 0; while (scanf("%d", &n) != EOF){ int r = n/2; if (n & 1) r++; int sum = 0; for (int i = 0; i < n; i++){ scanf("%d", &a[i]); sum += a[i]; } memset(dp,0,sizeof(dp)); dp[0][0] = 1; for (int i = 0; i < n; i++) for (int j = sum/2; j >= a[i]; j--) for (int k = r; k >= 1; k--) if (dp[j-a[i]][k-1]) dp[j][k] = 1; int ans = 0; for (int i = sum/2; i >= 0; i--){ if (n%2 == 0){ if (dp[i][r]){ ans = i; break; } } if (n%2 == 1){ if (dp[i][r] || dp[i][r-1]){ ans = i; break; } } } printf("%d %d\n", ans, sum-ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。