This problem can be solved by two methods

• Deepth First Search (DFS)
• Dynamic Programming (DP)

As I don’t know how to pruning, the first method will lead to Time Limit Exceed.

So, … this is my DP method:

State Transformation Equation:
    f(i, j) = 
        max(f(i-1, j), f(i-1, j-a(i)) + b(i))), if color(i-1, j) is BLACK and color(i - 1, j - a(i)) is BLACK,
        f(i-1,j-a(i))+b(i), if color(i-1,j) is WHITE and color(i-1,j-a(i)) is BLACK
    color(i, j) =
    	BLACK, if color(i-1, j) is BLACK or color(i-1, j-a(i)) is BLACK or (j-a(i)) = 0,
    	WHITE, if color(i-1, j) is WHITE and color(i-1, j-a(i)) is WHITE
    

Here is the source code:

``` cpp POJ 2184 Cow Exhibition #include #include using namespace std; int n,a[1010],b[1010]; #define N 200000 #define M 100000 int f[N+10],color[N+10]; int max(int x,int y){ return (x>y)?x:y; } int main(){ scanf("%d",&n); int i,j; for(i=0;i<n;i++){ scanf("%d%d",&a[i],&b[i]); if(a[i]<0&&b[i]<0)continue; if(a[i]>=0){ for(j=N-a[i];j>=0;j--){ if(color[j]){ if(color[j+a[i]]) f[j+a[i]]=max(f[j+a[i]],f[j]+b[i]); else f[j+a[i]]=f[j]+b[i]; color[j+a[i]]=1; } } } else{ for(j=-a[i];j<=N;j++){ if(color[j]){ if(color[j+a[i]]) f[j+a[i]]=max(f[j+a[i]],f[j]+b[i]); else f[j+a[i]]=f[j]+b[i]; color[j+a[i]]=1; } } } if(color[a[i]+M]==0){ color[a[i]+M]=1; f[a[i]+M]=b[i]; } } j=0; for(i=M;i<=N;i++){ if(color[i]&&f[i]>=0&&f[i]+i-M>j){ j=f[i]+i-M; } } printf("%d\n",j); return 0; }

```