这道题题意不想说了，跑了640ms，感觉水过去了，应该能通过单调队列优化,很长时间没碰已经不知道怎么写了，就说说现在的写法吧。
状态定义很关键:dp[i][j]把前j个topic放在前i堂课.
因为这道题中的topic不能跳，必须按顺序，那么我们可以用贪心先求出最少的课程数，凭感觉证明这个贪心的做法是准确的，且找不到反例。
然后根据dp前后状态递推方程：
dp[i][j]=max(dp[i][j],dp[i-1][k]+solve(k+1,j));(sum[k+1][j]<=L）
我们显然写个二重循环，里面再找k的时候写个循环，最差情况是O（n^3),前两个循环顺序随便写，其中一种写法快200ms，但感觉能用单调队列来把那个找k的直接优化成O（1)的做法，以后想到再补。
这道题格式很恶心，注意每个分块之间也要有空行。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<string>
using namespace std;
int cas,cass;
int l,c,n;
int t[1005];
int sum[1005];
int dp[1005][1005];
//dp[i][j]把前j个topic放在前i堂课
//dp[i][j]=max(dp[i][j],dp[i-1][k]+solve(k+1,j));(sum[k+1][j]<=L） int solve(int x)
{
if(x==0)
return 0;
else if(x>0&&x<=10)
return -c;
else
return (x-10)*(x-10);
}
int main()
{
// freopen("input.txt","r",stdin); scanf("%d",&cass);
while(cass--)
{
int cas=1;
while(scanf("%d",&n)==1&&n)
{
memset(sum,0,sizeof(sum));
if(cas>=2)
printf("\n");
printf("Case %d:\n\n",cas++);
scanf("%d%d",&l,&c);
for(int i=1;i<=n;i++)
{
scanf("%d",&t[i]);
if(i>1)
sum[i]=sum[i-1];
sum[i]+=t[i];
}
//贪心
int ans=1;
int cnt=0;
for(int i=1;i<=n;i++)
{
cnt+=t[i];
if(cnt>l)
{
ans++;
cnt=t[i];
}
}
//
printf("Minimum number of lectures: %d\n",ans);
memset(dp,0X7f,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=ans;i++)
for(int j=1;j<=n;j++)
{
for(int k=j-1;k>=0&&sum[j]-sum[k]<=l;k--)
dp[i][j]=min(dp[i][j],dp[i-1][k]+solve(l-(sum[j]-sum[k])));
}
printf("Total dissatisfaction index: %d\n",dp[ans][n]);
}
if(cass!=0)
printf("\n");
} }