| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
172ms过了,这题真的需要3000ms??#include <iostream>
using namespace std;
int N,L,C;
int t[1010];
int DI(int T){
if(!T) return 0;
if(T<=10) return -C;
return (T-10)*(T-10);
}
int main() {
int cse = 1;
while(1){
cin >> N;
if(!N) break;
cin >> L >> C;
for(int i = 1; i <= N; i++) cin >> t[i];
cout << "Case " << cse << ":" << endl << endl;
cse++;
int di[1010], lec[1010];
di[0] = 0, lec[0] = 0;
for(int i = 1; i <= N; i++){
int curT = i, aggT = t[i], mnLec = 2147483647, mnDI = 2147483647, argMn = -1;
while(curT > 0 && aggT <= L){
int newLec = lec[curT-1] + 1;
int newDI = DI(L-aggT) + di[curT-1];
if(newLec < mnLec || (newLec == mnLec && newDI < mnDI)){
mnDI = newDI;
mnLec = newLec;
argMn = curT;
}
curT--;
aggT += t[curT];
}
di[i] = mnDI;
lec[i] = mnLec;
}
cout << "Minimum number of lectures: " << lec[N] << endl;
cout << "Total dissatisfaction index: " << di[N] << endl << endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator