Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!
tweet

# dp

By: a guest on Dec 13th, 2012  |  syntax: None  |  size: 0.99 KB  |  views: 27  |  expires: Never
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
Top