本文主要是介绍uva 607 - Scheduling Lectures(贪心+记忆化搜索),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接: 607 - Scheduling Lectures
题目大意:给出课题数n,以及每堂课的时间l,以及常数c,然后是n个课题所需要的时间。
问题1:最少需要几节课时可以讲所有的课题讲完,并且课题的顺序不能调换,一个课题不能分在两节课讲。
问题2:在用的课时最少的情况下,如何让同学们的不满意度最低,不满意度的计算是根据课时的剩余时间t计算的,
解题思路:问题1可以用贪心的方法, 问题2用记忆化搜索。
#include <stdio.h>
#include <string.h>
const int N = 1005;
const int MAX = 1 << 30;
int min(int a, int b) { return a < b ? a : b; }int n, l, c, cnt, t[N], dp[N][N], vis[N][N];void handle() {memset(vis, 0, sizeof(vis));cnt = 0;int sum = 0;for (int i = 1; i <= n; i++) {sum += t[i];if (sum > l) {sum = t[i];cnt++;}}
}int get(int tmp) {if (tmp == 0) return 0;else if (tmp <= 10) return -c;else return (tmp - 10) * (tmp - 10);
}int solve(int x, int y) {if (vis[x][y]) return dp[x][y];int& ans = dp[x][y];if (x == 0)return y ? MAX : 0;else {ans = MAX;int sum = 0;for (int i = y; i > 0; i--) {sum += t[i];if (sum > l) break;int now = solve(x - 1, i - 1);if (now != MAX)ans = min(now + get(l - sum), ans);}vis[x][y] = 1;return ans;}
}int main() {int cas = 0;while (scanf("%d", &n), n) {scanf("%d%d", &l, &c);for (int i = 1; i <= n; i++)scanf("%d", &t[i]);handle();if (cas) printf("\n"); printf("Case %d:\n", ++cas);printf("Minimum number of lectures: %d\n", ++cnt);printf("Total dissatisfaction index: %d\n", solve(cnt, n));}return 0;
}
这篇关于uva 607 - Scheduling Lectures(贪心+记忆化搜索)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!