uva 607 - Sche易做图ng 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;  
}

补充：软件开发 , C++ ,