Advertisement
VladNitu

PrettyPrinting_Vlad

Jan 26th, 2023
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.39 KB | None | 0 0
  1. package weblab;
  2.  
  3. import java.util.List;
  4. import java.util.ArrayList;
  5.  
  6.  
  7. class Solution {
  8.  
  9.   static List<String> ans;
  10.  
  11.   static long[][] precomputSlack(int N, String[] words, int L) {
  12.      
  13.       long[][] S = new long[N + 1][N + 1];
  14.    
  15.       for (int i = 1; i <= N; ++i) {
  16.         int l = -1;
  17.         for (int j = i; j <= N; ++j)
  18.           {
  19.             l += (words[j].length() + 1);
  20.             if (l > L)
  21.               S[i][j] = Integer.MAX_VALUE / 2;
  22.             else
  23.               S[i][j] = L - l;
  24.           }
  25.       }  
  26.      
  27.       return S;
  28.    
  29.   }
  30.  
  31.   static long[] DP (long[][] S, int N) {
  32.     long[] OPT = new long[N + 1];
  33.     OPT[0] = 0; // Base case
  34.     for (int i = 1; i <= N; ++i) {
  35.       OPT[i] = Integer.MAX_VALUE / 2;
  36.       for (int k = 1; k <= i; ++k)
  37.         OPT[i] = Math.min(OPT[i], S[k][i] * S[k][i] + OPT[k-1]);
  38.     }
  39.    
  40.     return OPT;
  41.   }
  42.  
  43.   static void Reconstruct(long[] OPT, String[] words, long[][] S, int i) {
  44.     if (i == 0)
  45.       return;
  46.      
  47.     StringBuilder sb = new StringBuilder();
  48.    
  49.     int k = 1;  
  50.    
  51.     while (k <= i)
  52.       if (OPT[i] == S[k][i] * S[k][i] + OPT[k-1])
  53.         {
  54.           Reconstruct(OPT, words, S, k - 1);
  55.           for (int idx = k; idx <= i; ++idx)
  56.           if (i != idx)
  57.             sb.append(words[idx] + " ");
  58.           else
  59.             sb.append(words[idx]);
  60.            
  61.           ans.add(sb.toString());
  62.           break;
  63.         }
  64.       else k ++;
  65.    
  66.    
  67.    
  68.     return;
  69.   }
  70.  
  71.     /**
  72.      * @param L the maximum line length
  73.      * @param n the number of words
  74.      * @param words the actual words at indices 1 through n (including).
  75.      * @return
  76.      */
  77.     public static List<String> solve(int L, int N, String[] words) {
  78.         ans = new ArrayList<>();
  79.         long[][] S = precomputSlack(N, words, L);
  80.         // for (int i = 1; i <= N; ++i)
  81.         //   {
  82.         //     for (int j = 1; j <= N; ++j)
  83.         //       System.out.print(S[i][j] + " ");
  84.         //     System.out.println();
  85.         //   }
  86.        
  87.         long[] OPT = DP(S, N);
  88.         // for (int i = 0; i <= N; ++i)
  89.         // System.out.print(OPT[i] + " ");
  90.      
  91.         Reconstruct(OPT, words, S, N);
  92.        
  93.         // System.out.println(ans.size());
  94.         // for (String s: ans)
  95.         //   System.out.println(s);
  96.        
  97.         return ans;
  98.        
  99.     }
  100. }
  101.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement