Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

172ms过了,这题真的需要3000ms??

Posted by KatrineYang at 2017-01-21 06:26:18 on Problem 1513
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator