fork download 
  1. // Mochi Kasato - MKasato
  2. // FB: facebook.com/mochikasato/
  3. // Problem link: https://d...content-available-to-author-only...j.ca/problem/coci16c4p3
  4. #include <bits/stdc++.h>
  5. #define boostcode ios_base::sync_with_stdio(0); cin.tie(0);
  6. #define openf if (fopen("test.inp", "r")) {freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout);}
  7. #define fi first
  8. #define se second
  9. #define pb(x) push_back(x)
  10.  
  11. using namespace std;
  12. typedef long long ll;
  13. typedef pair<int, int> pii;
  14.  
  15. int n;
  16. int c[502];
  17. int dp[200002]; // dp[x]: Trạng thái cho biết tồn tại cách chia i vật dụng đầu
  18. int dp2[200002]; // Tương tự dp[x], nhưng dùng để xử lí với cách chia i+1 vật dụng đầu
  19.  
  20. int main() {
  21.     boostcode;
  22. //    openf;
  23.  
  24.     cin >> n;
  25.     for (int i = 1; i <= n; i++) cin >> c[i];
  26.     // Tính S = c[1] + c[2] + ... + c[n]:
  27.     int S = 0;
  28.     for (int i = 1; i <= n; i++) S += c[i];
  29.     // Xử lí quy hoạch động:
  30.     for (int x = 1; x <= S; x++) dp[x] = -1; // Ban đầu, để dp[x] = -1, ngoại trừ dp[0] (do ban đầu không lấy vật nào hết)
  31.     for (int i = 1; i <= n; i++) {
  32.         for (int x = 0; x <= S; x++) dp2[x] = -1;
  33.         for (int x = 0; x <= S; x++) {
  34.             if (dp[x] == -1) continue;
  35.             dp2[x] = max(dp2[x], dp[x]); // Không chia cho ai hết
  36.             dp2[abs(x-c[i])] = max(dp2[abs(x-c[i])], dp[x] + c[i]); // Chia cho bạn có phần nhỏ hơn
  37.             dp2[x+c[i]] = max(dp2[x+c[i]], dp[x] + c[i]); // Chia cho bạn có phần lớn hơn
  38.         }
  39.         for (int x = 0; x <= S; x++) dp[x] = dp2[x]; // lưu giá trị dp2[] và reset lại dp2[] cho những lần xử lí dp với i kế tiếp
  40.     }
  41.     // Tính kết quả bài toán cần tìm:
  42.     int T = (dp[0])/2;
  43.     int res = S - T;
  44.     cout << res;
  45.  
  46.     return 0;
  47. }
  48. /* TESTS:
  49. Test 1:
  50. 5
  51. 2
  52. 3
  53. 5
  54. 8
  55. 13
  56. -->
  57. 18
  58. */
  59.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
5
2
3
5
8
13
stdout 
18
https://ideone.com/m55dYG
language:
C++14 (gcc 8.3)
created:
47 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!