ZOJ Monthly, July 2012 - J : Watashi's BG
問題概要
長さN(<30)の配列Xがある。Xの部分和でMを越えない最大のものを求める問題。
解法
半分全列挙でよい。
acceptされたコード
#include <cstdio> #include <algorithm> #include <functional> using namespace std; typedef long long int64; const int64 INF = 1LL<<60; const int MAX_N = 32; int N, M; int as[MAX_N]; int64 nums[(1<<(MAX_N/2)) + 2]; bool init() { if (scanf("%d%d", &N, &M) == EOF) { return false; } for (int i = 0; i < N; ++i) { scanf("%d", as + i); } return N > 0; } int solve() { if (N == 1) { return as[0] <= M ? as[0] : 0; } const int half = N / 2; int L = 0; for (int bit = 0; bit < (1<<half); ++bit) { nums[L] = 0; for (int i = 0; i < half; ++i) if ((bit>>i)&1) { nums[L] += as[i]; } ++L; } nums[L++] = -INF; sort(nums, nums + L); reverse(nums, nums + L); int64 ans = -INF; for (int bit = 0; bit < (1<<(N-half)); ++bit) { int64 tmp = 0; for (int i = 0; i < N-half; ++i) if ((bit>>i)&1) { tmp += as[i+half]; } tmp += *lower_bound(nums, nums + L, M - tmp, greater<int64>()); if (tmp <= M && ans < tmp) { ans = tmp; } } return (int)ans; } int main() { for (;init();) { printf("%d\n", solve()); } return 0; }