本题目虽然比较简单，但也是一个非常好的题目；
有些地方需要说明一下；本题目要先用贪心发求出最优需要多少堂课，记最少需m；
然后以d[ i ][ j ] 表示前i节内容分给了前j节课后的最优满意度；然后动态规划即可；
一开始想到的最简单的dp为d[ i ][ j ][ k ]代表前i个内容占据的时间为j节课还多k分钟的时间，状态好转移；可惜复杂度太大会超时；
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf = 100000000;
const int maxn = 1010;
int n,L,C,a[maxn],st[maxn][505],m;
int fee(int t){
if(!t) return 0;
if(t>=1&&t<=10) return -C;
return (t-10)*(t-10);
}
int d[maxn][maxn];
bool vis[maxn][maxn];
int dp(int i,int j){
if(vis[i][j]) return d[i][j];
vis[i][j] = true;
if(i==n){
return d[i][j] = 0;
}
d[i][j] = inf;
int add=0;
for(int k=i+1;k<=n;k++){
add+=a[k];
if(add > L) break;
if(j<m)
d[i][j]=min(d[i][j],dp(k,j+1)+fee(L-add));
}
return d[i][j];
}
int main()
{
int kase=1;
while(scanf("%d",&n)==1&&n){
if(kase > 1) printf("\n");
scanf("%d %d",&L,&C);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int id = 0,use=0;
for(int i=0;i<=n;i++){
if(use+a[i] <= L){
use+=a[i];
}
else {
use = a[i]; id++;
}
}
if(use > 0) id++;
m=id;
memset(vis,false,sizeof(vis));
printf("Case %d:\n",kase++);
printf("Minimum number of lectures: %d\n",m);
printf("Total dissatisfaction index: %d\n",dp(0,0));
}
return 0;
}