Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package weblab;
- import java.util.List;
- import java.util.ArrayList;
- class Solution {
- static List<String> ans;
- static long[][] precomputSlack(int N, String[] words, int L) {
- long[][] S = new long[N + 1][N + 1];
- for (int i = 1; i <= N; ++i) {
- int l = -1;
- for (int j = i; j <= N; ++j)
- {
- l += (words[j].length() + 1);
- if (l > L)
- S[i][j] = Integer.MAX_VALUE / 2;
- else
- S[i][j] = L - l;
- }
- }
- return S;
- }
- static long[] DP (long[][] S, int N) {
- long[] OPT = new long[N + 1];
- OPT[0] = 0; // Base case
- for (int i = 1; i <= N; ++i) {
- OPT[i] = Integer.MAX_VALUE / 2;
- for (int k = 1; k <= i; ++k)
- OPT[i] = Math.min(OPT[i], S[k][i] * S[k][i] + OPT[k-1]);
- }
- return OPT;
- }
- static void Reconstruct(long[] OPT, String[] words, long[][] S, int i) {
- if (i == 0)
- return;
- StringBuilder sb = new StringBuilder();
- int k = 1;
- while (k <= i)
- if (OPT[i] == S[k][i] * S[k][i] + OPT[k-1])
- {
- Reconstruct(OPT, words, S, k - 1);
- for (int idx = k; idx <= i; ++idx)
- if (i != idx)
- sb.append(words[idx] + " ");
- else
- sb.append(words[idx]);
- ans.add(sb.toString());
- break;
- }
- else k ++;
- return;
- }
- /**
- * @param L the maximum line length
- * @param n the number of words
- * @param words the actual words at indices 1 through n (including).
- * @return
- */
- public static List<String> solve(int L, int N, String[] words) {
- ans = new ArrayList<>();
- long[][] S = precomputSlack(N, words, L);
- // for (int i = 1; i <= N; ++i)
- // {
- // for (int j = 1; j <= N; ++j)
- // System.out.print(S[i][j] + " ");
- // System.out.println();
- // }
- long[] OPT = DP(S, N);
- // for (int i = 0; i <= N; ++i)
- // System.out.print(OPT[i] + " ");
- Reconstruct(OPT, words, S, N);
- // System.out.println(ans.size());
- // for (String s: ans)
- // System.out.println(s);
- return ans;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement