每节课的长度为 L,有N个主题,讲每个主题的时间分别是 t1,t2,t3...,
每个主题必须在一节课讲完,不能分两节课。一节课可以将多个主题讲完
每节课上完有不满意度。
在所需课程数量最少的前提下,求最小不满意度。
#include <iostream> #include <cstring> #include <cmath> #include <algorithm> using namespace std ; const int N =1e3+3; int n,a[N],T[N],f[N],L,C ; // f[i] = min(f[j]+ (a[j+1]+...+a[i])) // s[i]-s[j]<=L int cal(int t){ if(t==0) return 0; else if(1<=t&&t<=10) return -C; else return (t-10)*(t-10); } void sov(int cas){ memset(f,127,sizeof f); T[0]=f[0]=0; for(int i=1;i<=n;i++){ T[i]=T[i-1]+1; f[i]=f[i-1]+cal(L-a[i]); int sum=a[i]; for(int j=i-1;j>=0;j--){ int tmp= f[j]+cal(L-sum); if(T[i]>T[j]+1){ T[i]=T[j]+1; f[i]=tmp; } else if(T[i]==T[j]+1&&tmp<f[i]){ f[i]=tmp; } sum+=a[j]; if(sum>L) break; } } if(cas) cout<<endl; cout << "Case "<<cas<<":" << endl; cout << "Minimum number of lectures: " << T[n] << endl; cout << "Total dissatisfaction index: " <<f[n] << endl; } signed main(){ int cas=0; while(cin>>n && n){ cin>>L>>C; for(int i=1;i<=n;i++) cin>>a[i]; sov(++cas); } }