#include <cstdio> #include <algorithm> using namespace std; const int MAX_DAY_SIZE = 8002; char schedule[MAX_DAY_SIZE]; const int NO_CAN_DO = -1000000; int meeting_pref[MAX_DAY_SIZE]; const char OFFICE_MEET = '1'; const char ONLINE_MEET = '2'; const char FREE_TIME = '3'; int best[3][MAX_DAY_SIZE][MAX_DAY_SIZE]; int main() { int day_size, miss_limit, travel_time; scanf("%d%d%d", &day_size, &miss_limit, &travel_time); scanf("%s", schedule + 1); int wyn = -1; for (int i = 1; i <= day_size; i++) { meeting_pref[i] = meeting_pref[i - 1] + (schedule[i] == FREE_TIME ? 0 : 1); } for (int travel_count = 0; travel_count <= 2; travel_count++) { for (int curr_time = 0; curr_time <= day_size; curr_time++) { for (int skipped = 0; skipped <= miss_limit; skipped++) { best[travel_count][curr_time][skipped] = NO_CAN_DO; } } } best[0][0][0] = 0; for (int travel_count = 0; travel_count <= 2; travel_count++) { for (int curr_time = 1; curr_time <= day_size; curr_time++) { for (int skipped = 0; skipped <= miss_limit; skipped++) { // Go to meeting if (schedule[curr_time] == ONLINE_MEET || (schedule[curr_time] == OFFICE_MEET && travel_count == 1)) { best[travel_count][curr_time][skipped] = max( best[travel_count][curr_time][skipped], best[travel_count][curr_time - 1][skipped] ); } // Have fun or work int fun_amount = travel_count == 1 ? 0 : 1; if (schedule[curr_time] == FREE_TIME) { best[travel_count][curr_time][skipped] = max( best[travel_count][curr_time][skipped], best[travel_count][curr_time - 1][skipped] + fun_amount ); } else if (skipped > 0) { best[travel_count][curr_time][skipped] = max( best[travel_count][curr_time][skipped], best[travel_count][curr_time - 1][skipped - 1] + fun_amount ); } // End travel now if (travel_count > 0 && curr_time >= travel_time) { int meetings_skipped = meeting_pref[curr_time] - meeting_pref[curr_time - travel_time]; if (skipped >= meetings_skipped) { best[travel_count][curr_time][skipped] = max( best[travel_count][curr_time][skipped], best[travel_count - 1][curr_time - travel_time][skipped - meetings_skipped] ); } } // printf("best[%d][%d][%d] = %d\n", travel_count, curr_time, skipped, best[travel_count][curr_time][skipped]); if (travel_count != 1 && curr_time == day_size) { wyn = max(wyn, best[travel_count][curr_time][skipped]); } } } } printf("%d\n", wyn); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | #include <cstdio> #include <algorithm> using namespace std; const int MAX_DAY_SIZE = 8002; char schedule[MAX_DAY_SIZE]; const int NO_CAN_DO = -1000000; int meeting_pref[MAX_DAY_SIZE]; const char OFFICE_MEET = '1'; const char ONLINE_MEET = '2'; const char FREE_TIME = '3'; int best[3][MAX_DAY_SIZE][MAX_DAY_SIZE]; int main() { int day_size, miss_limit, travel_time; scanf("%d%d%d", &day_size, &miss_limit, &travel_time); scanf("%s", schedule + 1); int wyn = -1; for (int i = 1; i <= day_size; i++) { meeting_pref[i] = meeting_pref[i - 1] + (schedule[i] == FREE_TIME ? 0 : 1); } for (int travel_count = 0; travel_count <= 2; travel_count++) { for (int curr_time = 0; curr_time <= day_size; curr_time++) { for (int skipped = 0; skipped <= miss_limit; skipped++) { best[travel_count][curr_time][skipped] = NO_CAN_DO; } } } best[0][0][0] = 0; for (int travel_count = 0; travel_count <= 2; travel_count++) { for (int curr_time = 1; curr_time <= day_size; curr_time++) { for (int skipped = 0; skipped <= miss_limit; skipped++) { // Go to meeting if (schedule[curr_time] == ONLINE_MEET || (schedule[curr_time] == OFFICE_MEET && travel_count == 1)) { best[travel_count][curr_time][skipped] = max( best[travel_count][curr_time][skipped], best[travel_count][curr_time - 1][skipped] ); } // Have fun or work int fun_amount = travel_count == 1 ? 0 : 1; if (schedule[curr_time] == FREE_TIME) { best[travel_count][curr_time][skipped] = max( best[travel_count][curr_time][skipped], best[travel_count][curr_time - 1][skipped] + fun_amount ); } else if (skipped > 0) { best[travel_count][curr_time][skipped] = max( best[travel_count][curr_time][skipped], best[travel_count][curr_time - 1][skipped - 1] + fun_amount ); } // End travel now if (travel_count > 0 && curr_time >= travel_time) { int meetings_skipped = meeting_pref[curr_time] - meeting_pref[curr_time - travel_time]; if (skipped >= meetings_skipped) { best[travel_count][curr_time][skipped] = max( best[travel_count][curr_time][skipped], best[travel_count - 1][curr_time - travel_time][skipped - meetings_skipped] ); } } // printf("best[%d][%d][%d] = %d\n", travel_count, curr_time, skipped, best[travel_count][curr_time][skipped]); if (travel_count != 1 && curr_time == day_size) { wyn = max(wyn, best[travel_count][curr_time][skipped]); } } } } printf("%d\n", wyn); } |