UVa-607, LiveArchive-5409, POJ-1513, TJU-1122, ZOJ-1183 : Scheduling Lectures

問題概要

長さL(<500)の講義がある。この講義にN(<1000)個のトピックを順に詰め込む。講義のあまり時間に応じてペナルティが課される。できるだけ少ない講義で、かつペナルティも最小にする問題。

解法

愚直だとO(N^2 * L)かかるが、DPの状態をあまり時間のみにすることで計算量をひとつ落とせる。

acceptされたコード

計算量O(N*L)。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 1000;
const int MAX_L = 500;
const int THRESHOLD = 10;
const int INF = 1<<29;

int N, L, C;
pair<int,int> dp[MAX_N+1][MAX_L+1];
int ts[MAX_N];

bool init(){
	scanf("%d", &N);
	if(N == 0){
		return false;
	}

	scanf("%d%d",&L, &C);
	for(int i=0; i<N; i++){
		scanf("%d", ts + i);
	}

	return true;
}

int sq(int x){
	return x * x;
}

void solve(){
	for(int i=0; i<=N; i++){
		fill(dp[i], dp[i] + MAX_L + 1, make_pair(INF, INF));
	}

	dp[0][0] = make_pair(0,0);
	for(int i=0; i<N; i++){
		for(int j=0; j<=L; j++)if(dp[i][j].first < INF){
			//詰め込む
			if(j + ts[i] <= L){
				dp[i+1][j + ts[i]] = min(dp[i+1][j + ts[i]], dp[i][j]);
			}

			//打ちきる
			if(j > 0){
				int extra = j == L ? 0 : L - j <= THRESHOLD ? -C : sq(L - j - 10);
				dp[i+1][ts[i]] = min(dp[i+1][ts[i]], make_pair(dp[i][j].first + 1, dp[i][j].second + extra));
			}
		}
	}

	for(int i=1; i<=L; i++){
		int extra = i == L ? 0 : L - i <= THRESHOLD ? -C : sq(L - i - 10);
		dp[N][i].second += extra;
	}

	pair<int,int> best(INF, INF);
	for(int i=0; i<=L; i++){
		best = min(dp[N][i], best);
	}
	printf("Minimum number of lectures: %d\n", best.first + 1);
	printf("Total dissatisfaction index: %d\n", best.second);
}

int main(){
	int c = 0;
	while(init()){
		if(c)puts("");
		printf("Case %d:\n", ++c);
		solve();
	}

	return 0;
}