The painter’s partition problem 1

You have to paint N boards of length {A0, A1, A2 … AN-1}. There are K painters available and you are also given how much time a painter takes to paint 1 unit of board. You have to get this job done as soon as possible under the constraints that any painter will only paint continuous sections of board, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

C++:
01 int painterPartition(int *A, int size, int k)
02 {
03     int *B=new int[size];
04     int *C=new int[size];
05     int *D=new int[size];
06     for(int i=0;i<size;i++)
07         B[i]=C[i]=D[i]=0;
08     C[size1]=D[size1]=B[size1]=A[size1];
09     for(int i=size2;i>=0;i){
10         B[i]=A[i]+B[i+1];
11         C[i]=B[i];
12     }
13     if(k==1)
14         return B[0];
15     int* P=C;
16     int* Q=D;
17     for(int i=2;i<=k;i++){
18         for(int j=0;j<size1;j++){
19             Q[j]=B[j]B[j+1]>P[j+1]?B[j]B[j+1]:P[j+1];
20             for(int t=2;t<sizej;t++){
21                 int w=B[j]B[j+t]>P[j+t]?B[j]B[j+t]:P[j+t];
22                 if(w<=Q[j])
23                     Q[j]=w;
24                 else
25                     break;
26 
27             }
28         }
29         int *tmp=P;
30         P=Q;
31         Q=P;
32     }
33     return P[0]<Q[0]?P[0]:Q[0];
34 }
Advertisements
This entry was posted in Dynamic programming. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s