题目大意：有n（n大于等于1小于等于1000）个主题，每个主题要花费t1,t2,……,tn（每个ti都不会大于L）的时间来讲，每个讲座L（L大于等于1小于等于500）分钟；安排讲座有两个规则：
不能讲一个主题分在两个讲座讲；
必须按顺序讲，即ti要在ti-1之后讲。
每个讲座都有一个DI值，（即不满意值）设t为提前下课的分钟数，则：
DI=0（若t=0）或DI=-C（若t大于等于1小于等于10）或DI=(t-10)的平方（若t大于10）。
求出最少安排多少个讲座能将所有主题讲完，并且求出在最少讲座的情况下不满意度的最小值是多少。
先用贪心，尽量把课往前安排，求出最少用多少次讲座可以讲完。记b[i]为前i个讲座最多包含的主题的数量（即前i个讲座最多包含b[i]个主题，再多就安排不下）；再从后往前贪心，记c[i]为前i个讲座最少包含的主题的数量（即前i个讲座最少安排c[i]个主题，否则就不能产生最优解了）。之后动态规划。d[i][j]表示前i个讲座包含j个主题最小的不满意值，用e[i][j]表示主题i到j安排在一个讲座内，DI值是多少。
状态转移方程：d[i][j]=min { d[i-1][u]+e[u+1][j] }（j从c[i]变化到b[i]，u从c[i-1]变化到b[i-1]）
#include<stdio.h>#include<stdlib.h>int a[1100];int b[1100];int c[1100];int d[1100][1100];int sum[1100][1100];int main(void){int i,j,n,m,p,q,u,v,min,co;co=0;scanf("%d",&n);while(n!=0){co++;scanf("%d%d",&m,&p);for(i=1;i<=n;i++){scanf("%d",&a[i]);}for(i=1;i<n;i++){sum[i][i]=a[i];for(j=i+1;j<=n;j++){sum[i][j]=sum[i][j-1]+a[j];}}sum[n][n]=a[n];u=0;v=1;for(i=1;i<=n;i++){if(u+a[i]>m){b[v]=i-1;i–;u=0;v++;}else{u=u+a[i];}}b[v]=n;c[v]=n;b[0]=v;u=0;v–;for(i=n;i>=1;i–){if(u+a[i]>m){c[v]=i;i++;u=0;v–;}else{u=u+a[i];}}for(u=c[1];u<=b[1];u++){if(sum[1][u]==m){d[1][u]=0;}else if(m-sum[1][u]>10){d[1][u]=(m-sum[1][u]-10)*(m-sum[1][u]-10);}else{d[1][u]=-p;}}for(i=2;i<=b[0];i++){for(u=c[i];u<=b[i];u++){min=100000000;for(v=c[i-1];v<=b[i-1];v++){if((v<=u)&&(sum[v+1][u]<=m)){if(sum[v+1][u]==m){q=d[i-1][v];}else if(m-sum[v+1][u]>10){q=d[i-1][v]+(m-sum[v+1][u]-10)*(m-sum[v+1][u]-10);}else{q=d[i-1][v]-p;}if(q<min){min=q;}}}d[i][u]=min;}}printf("Case %d:\n",co);printf("Minimum number of lectures: %d\n",b[0]);printf("Total dissatisfaction index: %d\n",d[b[0]][n]);scanf("%d",&n);if(n!=0){printf("\n");}}return 0;}
，突然之间失去了语言。那才是真正的寂寞，
