首页 > 代码库 > URAL 1005 Stone Pile

URAL 1005 Stone Pile

看数据规模,也懒得想了,裸DFS得了

 1 import java.util.Scanner; 2  3 public class P1005 4 { 5     private static int best = Integer.MAX_VALUE; 6  7     //a[] 原始值 8     //k 应该放第k块 9     //这个时候第一堆的值10     //这个时候第二堆的值11     private static void dfs(int a[], int k, int left, int right)12     {13         //放完了14         if (k == a.length)15         {16             best = Math.min(best, Math.abs(left - right));17             return;18         }19         //放到左边那堆20         dfs(a, k + 1, left + a[k], right);21         //放到又边那堆22         dfs(a, k + 1, left, right + a[k]);23     }24 25     public static void main(String args[])26     {27         try (Scanner cin = new Scanner(System.in))28         {29             while (cin.hasNext())30             {31                 int n = cin.nextInt();32                 int a[] = new int[n];33                 for (int i = 0; i < n; i++)34                     a[i] = cin.nextInt();35                 best = Integer.MAX_VALUE;36                 dfs(a, 0, 0, 0);37                 System.out.println(best);38             }39         }40     }41 }

 

URAL 1005 Stone Pile