cowexhibition.java

PKU中一些数据结构基本算法题的java实现

package PKU.DFS;
import java.util.Scanner;

/**
 * 
 */

/**
 * ID:2184
 * DFS+剪枝
 * @author yhm
 *
 */
public class CowExhibition {

	static int[] f,s;
	static int n,num;
	static int total;
	static int tF,tS;
	

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		n = cin.nextInt();
		total = tF = tS = num = 0;
		f = new int[n];
		s = new int[n];
	    int a,b;
	    for (int i=0; i<n; ++i)
	    {
	        a = cin.nextInt();
	        b = cin.nextInt();

	        if (a>=0 && b>=0)
	        {
	            total += a+b;
	            tF += a;
	            tS += b;
	        }
	        else if (a * b <=0)
	        {
	            if(a + b > 0)
	            {
	            	//以使SUM最大为目标
	                tF += a;
	                tS += b;
	                
	                //此个数据已经录入，取反使得后面的操作变为去掉本数据（SUM肯定减小，但可能变为合法）
	                a = -a;
	                b = -b;
	            }
	            //当没有进行上面if时，使得后面操作变为加上本数据（SUM肯定减小，但可能变为合法）
	            f[num]=a;
	            s[num]=b;
	            num++;
	        }
	    }
	    
	    int r = findProper(tF,tS,0);
	    System.out.println(r);

	}
	
	
	static int findProper(int tf,int ts,int idx)
	{
	    if (tf>=0 && ts>=0)
	    {
	        if (tf + ts >total)
	            total = tf + ts;
	        return tf+ts;
	    }
	    
	    //剪枝，继续后面的操作SUM肯定会减小，若已经有合法解，后面就没必要看了
	    if (idx>=num || tf + ts < total)
	        return 0;
	    
	    //要idx处的数据么？
	    int i = findProper(tf,ts,idx+1);
	    int j = findProper(tf+f[idx],ts+s[idx],idx+1);
	    return Math.max(i,j);
	}

}