srk.cpp

#include <iostream>
#include <algorithm>
#include <ctime>

using namespace std;

int N=100, K=3;
int A[100] = {4, 19, 29, 43, 45, 60, 67, 86, 90, 110, 130, 140, 154, 155, 162, 174, 183, 199, 219, 230, 238, 255, 256, 262, 277, 295, 302, 319, 325, 344, 352, 365, 384, 399, 406, 426, 430, 447, 463, 470, 480, 490, 501, 502, 517, 527, 529, 533, 535, 540, 550, 566, 583, 585, 588, 593, 601, 617, 627, 629, 634, 649, 663, 678, 689, 693, 698, 703, 720, 725, 730, 733, 735, 736, 755, 775, 787, 804, 824, 834, 840, 842, 845, 853, 872, 879, 892, 899, 902, 903, 922, 938, 956, 976, 992, 1001, 1016, 1018, 1022, 1032};
int last_vertex = -1;
int next_vertex[20001];
int DP1[10001][2] = { {0} };

int solution1_go(int top, bool isStart) {
	if (!isStart && next_vertex[top]==-1) {
		return 0;
	}
	if (DP1[top][isStart]) {
		return DP1[top][isStart];
	}
	if (isStart) {
		DP1[top][isStart] = solution1_go(top + K - 1, false) + K;
	}
	else
	{
		DP1[top][isStart] = min(solution1_go(top + 1, false) + 1, solution1_go(next_vertex[top], true));
	}
	return DP1[top][isStart];
}

int solution1() {
	sort(A, A + N);
	int last = -1;
	int j = N-1;
	last_vertex = A[j];
	for (int i = 20001; i >= 0; i--) {
		next_vertex[i] = last;
		if (A[j] == i) {
			last = i;
			j--;
		}
	}
	return solution1_go(A[0], true);
}

int solution2() {
	int DP2[101] = { 0xFFFFFF };

	/*move indices*/
	int B[101] = { 0 };
	for (int i = 0;i < N; i++) B[i] = A[i];
	sort(B, B + N);
	for (int i = N - 1; i >= 0; i--) B[i + 1] = B[i];
	B[0] = 0;
	
	DP2[1] = K;

	for (int i = 2; i <= N; i++) {
		for (int j = i; j > 0; j--) {
			DP2[i] = min(DP2[i], DP2[j - 1] + max(B[i] - B[j] + 1, K));
		}
	}
	return DP2[N];

}

int main()
{

	//N<=100
	//K<=10000

	//cin >> N >> K;
	//for (int i = 0; i < N; i++) cin >> A[i];

	clock_t begin1 = clock();
	int res1 = solution1();
	clock_t end1 = clock();
	double time1 = double(end1 - begin1) / CLOCKS_PER_SEC;

	cout << "Solution 1" << endl;
	cout << res1 << endl;
	cout << "Done in " << time1 << "ms" << endl;

	clock_t begin2 = clock();
	int res2 = solution2();
	clock_t end2 = clock();
	double time2 = double(end2 - begin2) / CLOCKS_PER_SEC;

	cout << "Solution 2" << endl;
	cout << res2 << endl;
	cout << "Done in " << time2 << "ms" << endl;

	

	return 0;
}