Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 1009 | Accepted: 433 |
Description
|0 if t=0 DI=|-C if 1 <= t <= 10 |(t-10)^2 otherwise
Input
Output
Sample Input
6 30 15 10 10 10 10 10 10 10 120 10 80 80 10 50 30 20 40 30 120 100 0
Sample Output
Case 1: Minimum number of lectures: 2 Total dissatisfaction index: 0 Case 2: Minimum number of lectures: 6 Total dissatisfaction index: 2700
Source
East Central North America 1998
题目大意:
你在讲述一个课程,它必须涵盖n个主题,每节课的时间为L,每个主题所需的时间分别为t1,t2......tn,对于每个主题,你必须决定它在那一节课内讲授,有两个限制条件:
1.每个主题必须在一节课内授完,不能分成两节课讲授
2.每个主题i必须在主题i+1之间讲授
由于上面的条件,每节课必然有些空闲时间,如果空闲时间不超过10分钟,学生会愉快的离开,如果空闲时间太多,学生会觉得浪费了学费,因此我们用公式为一节课的不满意指数(DI)建模
DI=0(t=0)
DI=-C(1<=t<=10)
DI=(t-10)*(t-10) (t>10)
其中C为一个正整数,t为一节课的空闲时间
你需要找到满足上述限制条件的最少讲课次数,如果有多个解,选择DI值最小的方案
最少讲课次数定义为数组minclass[],最小不满意指数定义为数组minsatisf[]
minclass[i]为主题1~i最少讲课次数,则:
minclass[i]=min(minclass[j])+1(0<=j<i),本质上就是将j+1和i分到一节课去
于是这段时间的sum:sum+=time[k](i<=k<=j+1),容易发现sum<L
minsatisf[i]=min(minsatisf[j]+DI(L-sum))(0<=j<i)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline void _read(int &x){
char t=getchar();bool sign=true;
while(t<'0'||t>'9')
{if(t=='-')sign=false;t=getchar();}
for(x=0;t>='0'&&t<='9';t=getchar())x=x*10+t-'0';
if(!sign)x=-x;
}
const int maxn=1005,inf=1e9;
int n,L,C,time[maxn],cases;
int minclass[maxn],minsatisf[maxn];
int DI(int t){
if(t==0)return 0;
if(t>=1&&t<=10)return -C;
if(t>10)return (t-10)*(t-10);
}
void DP(){
int i,j;
for(i=1;i<=n;i++){
minclass[i]=inf;
int sum=0;
for(j=i-1;j>=0;j--){
sum+=time[j+1];
if(sum>L)break;
if(minclass[i]<minclass[j]+1)continue;
int cost=minsatisf[j]+DI(L-sum);
if(minclass[i]==minclass[j]+1&&cost>=minsatisf[i])continue;
minclass[i]=minclass[j]+1;
minsatisf[i]=cost;
}
}
}
void CLEAR(){
memset(time,0,sizeof(time));
memset(minclass,0,sizeof(minclass));
memset(minsatisf,0,sizeof(minsatisf));
}
int main(){
while(scanf("%d",&n)==1&&n){
if(cases++)putchar(10);
CLEAR();
_read(L);_read(C);
for(int i=1;i<=n;i++)_read(time[i]);
printf("Case %d:\n\n",cases);
DP();
printf("Minimum number of lectures: %d\n",minclass[n]);
printf("Total dissatisfaction index: %d\n",minsatisf[n]);
}
}