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; }