CodePaste Logo
New Snippet New Snippet Recent Snippets Recent Snippets My Snippets My Snippets Web Code Search Snippets Search
Sign inor Register
Language: C++

Scheduling Lectures

49 Views
Copy Code Show/Hide Line Numbers
#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;
}
by amrmahdi
  September 03, 2010 @ 8:51am

Add a comment


Report Abuse
brought to you by:
West Wind Techologies



If you find this site useful and use it frequently please consider making a donation to support this free service.
Donate