ZOJ-1183-Scheduling Lectures

可以用贪心求最小讲课次数，贪心策略也很好想，就是对于任意主题，能早讲就早讲。这种方案的讲课次数一定是最少的，但是不满意指标不一定是最小，然后再利用动态规划求在最少讲课次数前提下的最小不满意指标。

方法一（自己想到的）

Accepted

C++11

1020

4240

#include "bits/stdc++.h"

using namespace std;

const int MAXN = ;

const int INF = 0x3f3f3f3f;

// arr[i]表示第i个主题所需时间，dp[u][j]表示第j个主题在第u节课讲的情况下前u节课的最小不满意指标

int arr[MAXN], dp[MAXN][MAXN];

int t, n, l, c;

// 计算不满意指标

int getDI(int k) {

    if (k == ) {

        return ;

    }

    if (k <= ) {

        return -c;

    }

    return (k - ) * (k - );

}

// 动态规划的实现，计算在最少讲课次数前提下的最小不满意指标

int getTDI(int m) {

    memset(dp, INF, sizeof(dp));

    dp[][] = ;

    for (int i = ; i <= n; i++) {

        int k = ;

        for (int j = i; j; j--) {

            k += arr[j];

            if (k <= l) {

                for (int u = ; u <= m; u++) {

                    dp[u][i] = min(dp[u][i], dp[u - ][j - ] + getDI(l - k));

                }

            }

        }

    }

    return dp[m][n];

}

int main() {

    scanf("%d", &t);

    while (t--) {

        int ca = ;

        while (scanf("%d", &n) && n) {

            int minLect = , k = ;

            scanf("%d%d", &l, &c);

            for (int i = ; i <= n; i++) {

                scanf("%d", &arr[i]);

                // 采用贪心求最小讲课次数

                k += arr[i];

                if (k > l) {

                    minLect++;

                    k = arr[i];

                }

            }

            if (ca != ) {

                puts("");

            }

            printf("Case %d:\n\n", ++ca);

            printf("Minimum number of lectures: %d\n", minLect);

            printf("Total dissatisfaction index: %d\n", getTDI(minLect));

        }

        if (t != ) {

            puts("");

        }

    }

    return ;

}

自定义函数getTDI里面的那句if (k <= l)应该改成if (k > l) {break;}的，脑抽了。

方法二（看了参考书之后改进的）

Accepted

1183

C++11

300

#include "bits/stdc++.h"

using namespace std;

const int MAXN = ;

const int INF = 0x3f3f3f3f;

// 每个主题需要的时间

int arr[MAXN];

// 主题1 ~ i (1 <= i < n)的最少讲课次数

int minLec[MAXN];

// 与主题相应的最小不满意指标

int minDis[MAXN];

int t, n, l, c;

// 计算不满意指标

int getDI(int k) {

    if (k == ) {

        return ;

    }

    if (k <= ) {

        return -c;

    }

    return (k - ) * (k - );

}

// 动态规划的实现，计算在最少讲课次数及相应的最小不满意指标

int dp() {

    memset(minLec, INF, sizeof(minLec));

    memset(minDis, INF, sizeof(minDis));

    minLec[] = minDis[] = ;

    for (int i = ; i <= n; i++) {

        int sum = ;

        for(int j = i; j; j--) {

            sum += arr[j];

            if (sum > l) {

                break;

            }

            if (minLec[j - ] +  < minLec[i]) {

                minLec[i] = minLec[j - ] + ;

                minDis[i] = minDis[j - ] + getDI(l - sum);

            }

            minDis[i] = min(minDis[i], minDis[j - ] + getDI(l - sum));

        }

    }

}

int main() {

    scanf("%d", &t);

    while (t--) {

        int ca = ;

        while (scanf("%d", &n) && n) {

            scanf("%d%d", &l, &c);

            for (int i = ; i <= n; i++) {

                scanf("%d", &arr[i]);

            }

            if (ca != ) {

                puts("");

            }

            printf("Case %d:\n\n", ++ca);

            dp();

            printf("Minimum number of lectures: %d\n", minLec[n]);

            printf("Total dissatisfaction index: %d\n", minDis[n]);

        }

        if (t != ) {

            puts("");

        }

    }

    return ;

}

从二维优化到一维极大的降低了时间复杂度和空间复杂度。果然还是很高明的。

巴特西

ZOJ-1183-Scheduling Lectures

最新文章

热门文章