Language: C++
Scheduling Lectures
#include<iostream> using namespace std; int n , L, C; int dp[1001][501]; int topics[1001]; int needed; #define oo (int)1e9 inline int DI(int left) { if ( !left ) return 0; if( left <= 10 ) return -C; return (left-10)*(left-10); } bool visited[1001][502]; inline bool canBe(int ind , int time, int lec) { for(int i = ind ; i < n ; ++i) { if( time - topics[i] >= 0 ) time -= topics[i]; else { ++lec; time = L; --i; } } return lec+1 == needed; } int calc(int ind , int time, int lec) { if( ind == n && lec+1 == needed ) return DI(time); if( !canBe(ind,time,lec) ) return oo; if( visited[ind][time] ) return dp[ind][time]; int ret = oo , a , b; if( time - topics[ind] >= 0 ) { a = calc(ind+1,time-topics[ind],lec); b = calc(ind,L,lec+1); if( b < oo ) b += DI(time); if( a < oo || b < oo ) ret = min(a,b); } else { a = calc(ind,L,lec+1); if( a < oo ) ret = a + DI(time); } visited[ind][time] = true; return dp[ind][time] = ret; } int main() { int cases = 1; while( scanf("%d",&n) && n ) { scanf("%d%d",&L,&C); for(int i = 0 ; i < n ; ++i) scanf("%d",topics+i); if( cases > 1 ) puts(""); needed = 0; int sum; for(int i = 0 ; i < n ; ++i) { sum = 0; int j = i; while( j < n ) { sum += topics[j]; if( sum > L ) { i = j-1; needed++; break; } if( j == n-1 ) { i = j; needed++; break; } ++j; } } memset(visited,false,sizeof visited); printf("Case %d:\nMinimum number of lectures: %d\nTotal dissatisfaction index: %d\n",cases++,needed,calc(0,L,0)); } return 0; }
Report Abuse
Subscribe
Discuss
What's new
What is it
New Snippet
Recent Snippets
My Snippets
Web Code
Search

