UVa 607

focus on minimum lectures first, i must come before i+1, so we have
state:
    dp[i] - minimum lectures overlaps i topics
transition:
    dp[i]=min(dp[j]+1), for all 0<j<i and L-(t[i]-t[j])>0
    L-(t[i]-t[j])>0 means time left is enough to overlap t[j] till t[i] only when minimum lectures of two equals shall we consider about minimum DI
state:
    dp[i] - minimum DI overlaps i topics
transition:
    dp[i]=min(dp[j]+DI(L-(t[i]-t[j])), for all 0<j<i and L-(t[i]-t[j])>0

/* UVas */
/*****************************************************************************/
int n, L, C, c=1;
int t[1001];
int d1[1001];
int d2[1001];
int di(int time) {
    return time==0?0:time<=10?-C:(time-10)*(time-10);
}
int main(void) {
    while (cin>>n&&n) {
        cin>>L>>C;
        if (c>1) {
            cout<<endl;
        }
        for (int i=1; i<=n; i++) {
            cin>>t[i];
            t[i]+=t[i-1];
        }
        memset(d1, -1, sizeof(d1));
        memset(d2, -1, sizeof(d2));
        d1[0]=0;
        d2[0]=0;
        for (int i=1; i<=n; i++) {
            for (int j=i-1; j>=0&&t[i]-t[j]<=L; j--) {
                int d=di(L-(t[i]-t[j]));
                if (d1[i]<0||d1[i]>d1[j]+1) {
                    d1[i]=d1[j]+1;
                    d2[i]=d2[j]+d;
                }
                if (d1[i]==d1[j]+1&&(d2[i]>d2[j]+d||d2[i]==-1)) {
                    d2[i]=d2[j]+d;
                }
            }
        }
        cout<<"Case "<<c<<":"<<endl;
        cout<<"Minimum number of lectures: "<<d1[n]<<endl;
        cout<<"Total dissatisfaction index: "<<d2[n]<<endl;
        c++;
    }
    return 0;
}
/*****************************************************************************/