fork(1) download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <cstdlib>
  6. #include <math.h>
  7. #include <cmath>
  8. #include <algorithm>
  9. #define rep(i, n) for(LL i = 0; i < n; i++)
  10. typedef long long LL;
  11. using namespace std;
  12.  
  13. const LL N=1010;
  14. LL a[N], dp[N][N], lchap;
  15. LL n;
  16. vector <LL> out1, out2;
  17.  
  18. LL solve(LL pos, LL saf, LL chap)
  19. {
  20.     if (dp[pos][saf] && chap != 1) return dp[pos][saf];
  21.     if (pos == -1) {
  22.         if (chap) lchap = saf + 1;
  23.         return a[saf];
  24.     }
  25.     if (pos == 0) {
  26.         if (chap) cout << saf + 1 << ' ' << 0 + 1 << endl;
  27.         return max(a[0], a[saf]);
  28.     }
  29.     LL p1 = solve(pos - 2, saf, 0) + max(a[pos], a[pos - 1]);
  30.     LL p2 = solve(pos - 2, pos - 1, 0) + max(a[pos], a[saf]);
  31.     LL p3 = solve(pos - 2, pos, 0) + max(a[pos - 1], a[saf]);
  32.  
  33.     LL mx = min(p1, min(p2, p3));
  34.     p1 *= (p1 == mx); p2 *= (p2 == mx); p3 *= (p3 == mx);
  35.  
  36.     if (p1 && chap) solve(pos - 2, saf, 1), cout << pos + 1 << ' ' << pos - 1 + 1 << endl;
  37.     else if (p2 && chap) solve(pos - 2, pos - 1, 1), cout << pos + 1 << ' ' << saf + 1 << endl;
  38.     else if (p3 && chap) solve(pos - 2, pos, 1), cout << pos - 1 + 1 << ' ' << saf + 1 << endl;
  39.     return dp[pos][saf] = mx;
  40. }
  41.  
  42. int main()
  43. {
  44.     ios_base::sync_with_stdio(false);
  45.     cin >> n;
  46.     rep(i, n)
  47.         cin >> a[i];
  48.     reverse(a, a + n);
  49.     cout << solve(n - 2, n - 1, 0) << endl;
  50.     solve(n - 2, n - 1, 1);
  51.     if (lchap) cout << lchap << endl;
  52.     return 0;
  53. }
Success #stdin #stdout 0s 11456KB
comments (?)
stdin
copy 
5
2 4 3 1 4
stdout
copy 
-9138260219401992056
1 4
3 5
2
https://ideone.com/EIR6MZ
language:
C++14 (gcc 8.3)
created:
10 years 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!