Poj Solution 2385

http://poj.org/problem?id=2385

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;

public class Main {

    /**
     * @param args
     */
    public static int max(int x,int y)
    {
        if(x>y) return x;
        return y;
    }
    
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        
        int t,w,i,j,k,ans=0;
        int dp[][][]=new int[1005][35][2];
        int way[]=new int[1005];
        
        for(i=0;i< 1005;++i) for(j=0;j< 35;++j) for(k=0;k< 2;++k)
            dp[i][j][k]=0;
        
        Scanner cin = new Scanner(System.in);
        
        t = cin.nextInt();
        w = cin.nextInt();
        
        for(i=1;i<=t;++i)
            way[i]=cin.nextInt()-1;
        
        for(i=1;i<=t;++i) for(j=0;j<=w;++j) for(k=0;k< 2;++k)
        {
          if(way[i]==k)
            dp[i][j][k]=max(dp[i-1][j][k]+1,j>0?dp[i-1][j-1][1-k]+1:1);
          else dp[i][j][k]=max(dp[i-1][j][k],j>0?dp[i-1][j-1][1-k]:0);
          if(dp[i][j][k]>ans&&((k==1&&j< w)||(k==0&&j<=w))) ans=dp[i][j][k];
        }
        
        System.out.println(ans);
    }

}

											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *