#1
by ワニ » 1年前
とあるonline judgeの問題を書きました。時間計算量が大きいためtime exceedと表示されます。時間計算量を削減するため、メモ化にしたいのです。
以下は、再帰で実装したcodeで、メモ化したいcodeです。
[code]#include <stdio.h> // scanf, printf
#include <string.h> // memset, memchr
int max(int a, int b) { return a > b ? a : b; }
int knapsack(int w, int a[], int b[], int n, char t[])
{
if (--n < 0) return w;
int len = b[n] - a[n];
if (memchr(t + a[n], 1, len)) return knapsack(w, a, b, n, t);
memset(t + a[n], 1, len);
int k = knapsack(w + len, a, b, n, t);
memset(t + a[n], 0, len);
return max(k, knapsack(w, a, b, n, t));
}
int main(void)
{
int number_of_client, max = 0, start, end;
scanf("%d", &number_of_client);
int jobs_start[number_of_client], jobs_end[number_of_client];
for (int i = 0; i < number_of_client; i++) {
scanf("%d%d", &jobs_start[i], &jobs_end[i]);
if (jobs_end[i] > max) max = jobs_end[i];
}
scanf("%d%d", &start, &end);
if (end > max) max = end;
char t[max];
memset(t, 1, max);//tを初期化
memset(t + start, 0, end - start);
printf("%d\n", knapsack(0, jobs_start, jobs_end, number_of_client, t));
}
[/code]
Description:
現在、サスケは複数のクライアントから依頼を受け取っており、各依頼にはクライアントが指定した開始日と完了日があります(必要な稼働日数は完了日から開始日を引いたものです)サスケはどの注文を約束するかを知りませんでした。
複数のクライアントによって指定された開始日と完了日、およびサスケの作業の開始日と終了日を知っているので、サスケが最大の収入を得ることができるように、サスケがクライアントの依頼を選択するのを手伝ってください。
たとえば、サスケは7つのクライアントの依頼を受け取り、指定された日付と完了日は{[6、10]、[10,12]、[8,13]、[3,7]、[1,6]、[13 、16]、[5、9]}、サスケが{[1,6]、[6,10]、[10,12]、[13,16]を選択した場合、サスケは1日目から16日目まで動作することが知られています。 ]}これら4人の顧客の手数料であるサスケの収入が最も多く、合計で5 + 4 + 2 + 3=14日間の収入があります。マリオが3日目から12日目まで働く場合は、{[3,7]、[10,12]}または{[5、9]、[10、12]}または{[6、10]、[10、12 ]}手数料、マリオが最も収入があり、合計4 + 2=6日間の収入です。
sample input
7
6 10
10 12
8 13
3 7
1 6
13 16
5 9
1 16
sample output
14
とあるonline judgeの問題を書きました。時間計算量が大きいためtime exceedと表示されます。時間計算量を削減するため、メモ化にしたいのです。
以下は、再帰で実装したcodeで、メモ化したいcodeです。
[code]#include <stdio.h> // scanf, printf
#include <string.h> // memset, memchr
int max(int a, int b) { return a > b ? a : b; }
int knapsack(int w, int a[], int b[], int n, char t[])
{
if (--n < 0) return w;
int len = b[n] - a[n];
if (memchr(t + a[n], 1, len)) return knapsack(w, a, b, n, t);
memset(t + a[n], 1, len);
int k = knapsack(w + len, a, b, n, t);
memset(t + a[n], 0, len);
return max(k, knapsack(w, a, b, n, t));
}
int main(void)
{
int number_of_client, max = 0, start, end;
scanf("%d", &number_of_client);
int jobs_start[number_of_client], jobs_end[number_of_client];
for (int i = 0; i < number_of_client; i++) {
scanf("%d%d", &jobs_start[i], &jobs_end[i]);
if (jobs_end[i] > max) max = jobs_end[i];
}
scanf("%d%d", &start, &end);
if (end > max) max = end;
char t[max];
memset(t, 1, max);//tを初期化
memset(t + start, 0, end - start);
printf("%d\n", knapsack(0, jobs_start, jobs_end, number_of_client, t));
}
[/code]
Description:
現在、サスケは複数のクライアントから依頼を受け取っており、各依頼にはクライアントが指定した開始日と完了日があります(必要な稼働日数は完了日から開始日を引いたものです)サスケはどの注文を約束するかを知りませんでした。
複数のクライアントによって指定された開始日と完了日、およびサスケの作業の開始日と終了日を知っているので、サスケが最大の収入を得ることができるように、サスケがクライアントの依頼を選択するのを手伝ってください。
たとえば、サスケは7つのクライアントの依頼を受け取り、指定された日付と完了日は{[6、10]、[10,12]、[8,13]、[3,7]、[1,6]、[13 、16]、[5、9]}、サスケが{[1,6]、[6,10]、[10,12]、[13,16]を選択した場合、サスケは1日目から16日目まで動作することが知られています。 ]}これら4人の顧客の手数料であるサスケの収入が最も多く、合計で5 + 4 + 2 + 3=14日間の収入があります。マリオが3日目から12日目まで働く場合は、{[3,7]、[10,12]}または{[5、9]、[10、12]}または{[6、10]、[10、12 ]}手数料、マリオが最も収入があり、合計4 + 2=6日間の収入です。
sample input
7
6 10
10 12
8 13
3 7
1 6
13 16
5 9
1 16
sample output
14