fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.  
  7.         int n = sc.nextInt();
  8.  
  9.         long[] A = new long[n + 1]; // no neighbor
  10.         long[] B = new long[n + 1]; // one neighbor
  11.         long[] C = new long[n + 1]; // both neighbors
  12.  
  13.         for (int i = 1; i <= n; i++) A[i] = sc.nextLong();
  14.         for (int i = 1; i <= n; i++) B[i] = sc.nextLong();
  15.         for (int i = 1; i <= n; i++) C[i] = sc.nextLong();
  16.  
  17.         //We don’t construct the permutation explicitly. 
  18.         //Instead, we enforce local ordering constraints between adjacent processors. 
  19.         //These local constraints are sufficient to guarantee a globally valid ordering
  20.  
  21.         long[][] dp = new long[n + 1][4];
  22.  
  23.         // initialize with very small values
  24.         for (int i = 0; i <= n; i++) {
  25.             Arrays.fill(dp[i], Long.MIN_VALUE);
  26.         }
  27.         /*
  28.         “The exact global order is hard, but what matters is only relative ordering between adjacent processors.”
  29.         👉 So I don’t care about full permutation
  30.         only care about:
  31.         i vs (i-1)
  32.         i vs (i+1)
  33.         */
  34.         dp[1][3] = A[1]; // neither neighbor
  35.         dp[1][2] = B[1]; // one neighbor possible
  36.         // dp[1][0], dp[1][1] invalid
  37.  
  38.         // 🔄 Fill DP
  39.         for (int i = 2; i <= n; i++) {
  40.  
  41.             // col 0 → both neighbors already processed
  42.             // need (i-1) before i
  43.             dp[i][0] = Math.max(dp[i-1][1], dp[i-1][3]) + C[i];
  44.  
  45.             // col 1 → left done, right not yet
  46.             // (i-1) before i
  47.             dp[i][1] = Math.max(dp[i-1][1], dp[i-1][3]) + B[i];
  48.  
  49.             // col 2 → right done, left not yet
  50.             // i before (i-1)
  51.             dp[i][2] = Math.max(dp[i-1][0], dp[i-1][2]) + B[i];
  52.  
  53.             // col 3 → neither done yet
  54.             // i before (i-1)
  55.             dp[i][3] = Math.max(dp[i-1][0], dp[i-1][2]) + A[i];
  56.         }
  57.  
  58.         // ❗ invalid end cases (no right neighbor exists for n)
  59.         dp[n][0] = Long.MIN_VALUE;
  60.         dp[n][2] = Long.MIN_VALUE;
  61.  
  62.         long ans = Long.MIN_VALUE;
  63.         for (int j = 0; j < 4; j++) {
  64.             ans = Math.max(ans, dp[n][j]);
  65.         }
  66.  
  67.         System.out.println(ans);
  68.     }
  69. }
Success #stdin #stdout 0.11s 54420KB
comments (?)
stdin
copy 
4
1 2 3 4
4 4 2 1
1 1 1 1
stdout
copy 
14
https://ideone.com/bJw1Oc
language:
Java (HotSpot 12)
created:
4 hours ago
visibility:
public

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!