fork download
  1. using System;
  2. using System.Linq;
  3.  
  4. // (づ°ω°)づミ★゜・。。・゜゜・。。・゜☆゜・。。・゜゜・。。・゜
  5. public class Solver
  6. {
  7. static void Main()
  8. {
  9. int n = int.Parse(Console.ReadLine());
  10. var a = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
  11.  
  12. var dp1 = new int[n + 1, 3 * n + 1];
  13. var dp2 = new int[n + 1, 3 * n + 1];
  14. for (int i = 0; i < 3 * n; i++)
  15. {
  16. for (int j = 0; j <= n; j++)
  17. {
  18. dp1[j, i + 1] = Math.Max(dp1[j, i + 1], dp1[j, i]);
  19. dp2[j, i + 1] = Math.Max(dp2[j, i + 1], dp2[j, i]);
  20. if (j < n && i < 3 * n - 1)
  21. {
  22. dp1[j + 1, i + 2] = Math.Max(dp1[j + 1, i + 2], dp1[j, i] + a[i]);
  23. dp2[j + 1, i + 2] = Math.Max(dp2[j + 1, i + 2], dp2[j, i] + a[i + 1]);
  24. }
  25. }
  26. }
  27.  
  28. Console.WriteLine(Math.Max(dp1[n, 3 * n], dp2[n, 3 * n]));
  29. }
  30. }
Success #stdin #stdout 0.05s 34016KB
stdin
2
14 11 6 3 22 20
stdout
36