Click here to Skip to main content
15,868,141 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
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");
	}
}


What I have tried:

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");
	}
}
Posted
Comments
Dave Kreskowiak 22-Jan-23 1:12am    
Resolve what issue? You never explained what the problem is.
OriginalGriff 22-Jan-23 1:58am    
This is not a good question - we cannot work out from that little what you are trying to do.
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.

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