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

• 方法一（自己想到的）

  Accepted

  1183

  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

  10

  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 ;
  }

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