15,617,168 members

See more:

import java.util.*; import java.io.*; import java.lang.*; public class Abhinav { public final int N = 4e5; public static final int M = 110; public static final int inf = 0x3f3f3f3f; public int[] a = new int[N]; public int[][] dp = new int[N][M]; public int[] lst = new int[N]; public int[] pre = new int[N]; public int[] nxt = new int[N]; public int i; public int j; public int n; public int m; public int L; public int R; public int sum; public int cal(int l, int r) { while (L < l) { if (nxt[L] <= R) { sum -= nxt[L] - L; } L++; } while (L > l) { --L; if (nxt[L] <= R) { sum += nxt[L] - L; } } while (R < r) { ++R; if (pre[R] >= L) { sum += R - pre[R]; } } while (R > r) { if (pre[R] >= L) { sum -= R - pre[R]; } R--; } return sum; } public void solve(int l, int r, int L1, int R1, int now) { if (l > r || L1 > R1) return; int mid = (l + r) / 2; int val = inf; int pos; for (int i = L1; i < mid && i < = R1; ++i) { int tmp = dp[i][now - 1] + cal(i + 1, mid); if (tmp < val) { pos = i; val = tmp; } } dp[mid][now] = val; solve(l, mid - 1, L1, pos, now); solve(mid + 1, r, pos, R1, now); } public static int main(String args[]) { Scanner sc = new Scanner(System.in); ios.sync_with_stdio(false); n = sc.nextInt(); m = sc.nextInt(); for (i = 1; i <= n; ++i) { sc.nextInt(a[i]); } for (i = 1; i <= n; ++i) { dp[i][0] = inf; pre[i] = lst[a[i]]; lst[a[i]] = i; } for (i = 1; i <= n; ++i) { lst[a[i]] = n + 1; } for (i = n; i != 0; --i) { nxt[i] = lst[a[i]]; lst[a[i]] = i; } for (i = 1; i <= m; ++i) { solve(1, n, 0, n, i); } System.out.print(dp[n][m]); System.out.print("\n"); } }

import java.util.*; import java.io.*; import java.lang.*; public class Abhinav { public final int N = 4e5; public static final int M = 110; public static final int inf = 0x3f3f3f3f; public int[] a = new int[N]; public int[][] dp = new int[N][M]; public int[] lst = new int[N]; public int[] pre = new int[N]; public int[] nxt = new int[N]; public int i; public int j; public int n; public int m; public int L; public int R; public int sum; public int cal(int l, int r) { while (L < l) { if (nxt[L] <= R) { sum -= nxt[L] - L; } L++; } while (L > l) { --L; if (nxt[L] <= R) { sum += nxt[L] - L; } } while (R < r) { ++R; if (pre[R] >= L) { sum += R - pre[R]; } } while (R > r) { if (pre[R] >= L) { sum -= R - pre[R]; } R--; } return sum; } public void solve(int l, int r, int L1, int R1, int now) { if (l > r || L1 > R1) return; int mid = (l + r) / 2; int val = inf; int pos; for (int i = L1; i < mid && i < = R1; ++i) { int tmp = dp[i][now - 1] + cal(i + 1, mid); if (tmp < val) { pos = i; val = tmp; } } dp[mid][now] = val; solve(l, mid - 1, L1, pos, now); solve(mid + 1, r, pos, R1, now); } public static int main(String args[]) { Scanner sc = new Scanner(System.in); ios.sync_with_stdio(false); n = sc.nextInt(); m = sc.nextInt(); for (i = 1; i <= n; ++i) { sc.nextInt(a[i]); } for (i = 1; i <= n; ++i) { dp[i][0] = inf; pre[i] = lst[a[i]]; lst[a[i]] = i; } for (i = 1; i <= n; ++i) { lst[a[i]] = n + 1; } for (i = n; i != 0; --i) { nxt[i] = lst[a[i]]; lst[a[i]] = i; } for (i = 1; i <= m; ++i) { solve(1, n, 0, n, i); } System.out.print(dp[n][m]); System.out.print("\n"); } }

Comments

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CodeProject,
20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8
+1 (416) 849-8900

Remember that we can't see your screen, access your HDD, or read your mind - we only get exactly what you type to work with - we get no other context for your project.

Imagine this: you go for a drive in the country, but you have a problem with the car. You call the garage, say "it broke" and turn off your phone. How long will you be waiting before the garage arrives with the right bits and tools to fix the car given they don't know what make or model it is, who you are, what happened when it all went wrong, or even where you are?

That's what you've done here. So stop typing as little as possible and try explaining things to people who have no way to access your project!

Use the "Improve question" widget to edit your question and provide better information.