Want more features on Pastebin? Sign Up, it's FREE!
Guest

dp

By: a guest on Dec 13th, 2012  |  syntax: None  |  size: 0.99 KB  |  views: 27  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. using namespace std;
  2.  
  3. #include<iostream>
  4. #include<cstring>
  5. #include<cmath>
  6.  
  7. #define max(a,b) (((a)>(b))?(a):(b))
  8. #define N 50000
  9.  
  10. //int max(int a, int b) { return (a > b)? a : b; }
  11.  
  12. /*int iabs(int n)
  13. {
  14.     return (n > 0)? n : -n;
  15. }*/
  16.  
  17. int dp[105][N],val[N],n,maxV;
  18.  
  19. int solve(int item,int W)
  20. {
  21.     if(item>n)
  22.         return 0;
  23.     if(dp[item][W]!=-1)
  24.         return dp[item][W];
  25.  
  26.     if(maxV>=(W+val[item]))
  27.         return dp[item][W] = max(val[item]+solve(item+1,W+val[item]),solve(item+1,W));
  28.     else
  29.         return dp[item][W] = solve(item+1,W);
  30. }
  31.  
  32. int main()
  33. {
  34.     int T;
  35.     cin>>T;
  36.  
  37.     while(T--)
  38.     {
  39.         int sum=0;
  40.         memset(dp,-1,sizeof(dp));
  41.         cin>>n;
  42.         for(int i=1;i<=n;i++)
  43.         {
  44.             cin>>val[i];
  45.             sum+=val[i];
  46.         }
  47.        /* if(sum%2)
  48.             maxV = (sum/2)+1;
  49.         else*/
  50.             maxV = sum/2;
  51.         int ans = solve(1,0);
  52.         cout<<(sum-ans)-ans<<endl;
  53.     }
  54.     return 0;
  55. }
clone this paste RAW Paste Data