+/EE360C
algorithms
git clone https://git.julia.blue/+/EE360C
3424b96
master
1public class Program3 { 2static int [][]sums ; 3static int [][]best ; 4 5static int sum (int start ,int end ) { 6int temp =end ; 7while (sums [start ][temp ] == -1 ) { --temp ; } 8while (temp ++ !=end ) { 9sums [start ][temp ] =sums [start ][temp -1 ] +sums [temp ][temp ]; 10 } 11return sums [start ][end ]; 12 } 13 14static int diff (int l ,int m ,int r ) { 15int temp =Math .min (maximize (l ,m ) +sum (l ,m ), 16maximize (m +1 ,r ) +sum (m +1 ,r )); 17return temp ; 18 } 19 20static int maximize_linear (int start ,int end ) { 21if (best [start ][end ] != -1 ) { 22return best [start ][end ]; 23 } 24int max =0 ; 25int max_index = -1 ; 26int diff =0 ; 27for (int i =start ;i <end ; ++i ) { 28int left =maximize_linear (start ,i ) +sum (start ,i ); 29int right =maximize_linear (i +1 ,end ) +sum (i +1 ,end ); 30if ((diff =Math .min (left ,right )) >max ) { 31max =diff ; 32max_index =i ; 33 } 34 } 35int left =maximize (start ,max_index ) +sum (start ,max_index ); 36int right =maximize (max_index +1 ,end ) +sum (max_index +1 ,end ); 37return best [start ][end ] =Math .min (left ,right ); 38 } 39 40static int maximize (int start ,int end ) { 41if (best [start ][end ] != -1 ) { 42return best [start ][end ]; 43 } 44if (end -start ==1 ) { 45return best [start ][end ] = 46Math .min (sums [start ][start ],sums [end ][end ]); 47 } 48if (end -start <=10 ) { 49return maximize_linear (start ,end ); 50 } 51int r =end ; 52int l =start ; 53int m = (r +l ) /2 ; 54while (r -l >1 ) { 55int ldiff =diff (start ,m -1 ,end ); 56int mdiff =diff (start ,m ,end ); 57if (mdiff >=ldiff ) { 58int rdiff =diff (start ,m +1 ,end ); 59if (mdiff >=rdiff ) { 60break ; 61 } 62l =m +1 ; 63 }else { 64r =m -1 ; 65 } 66m = (r +l ) /2 ; 67if (m ==l ) { 68mdiff =diff (start ,m ,end ); 69int temp =diff (start ,m +1 ,end ); 70if (temp >mdiff ) { 71 ++m ; 72 } 73 } 74 } 75int left =maximize (start ,m ) +sum (start ,m ); 76int right =maximize (m +1 ,end ) +sum (m +1 ,end ); 77return best [start ][end ] =Math .min (left ,right ); 78 } 79 80public static int maxCoinValue (int []cities ) { 81int n =cities .length ; 82sums =new int [n ][n ]; 83best =new int [n ][n ]; 84for (int i =0 ;i <n ; ++i ) { 85for (int j =0 ;j <n ; ++j ) { 86if (i ==j ) { 87sums [i ][j ] =cities [i ]; 88best [i ][j ] =0 ; 89 }else { 90sums [i ][j ] = -1 ; 91best [i ][j ] = -1 ; 92 } 93 } 94 } 95int total =0 ; 96int start =0 ; 97int end =n -1 ; 98return maximize (start ,end ); 99 } 100}