Advertisement
Guest User

dp dp dp dp dp dp

a guest
Sep 20th, 2019
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.14 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define pii pair <int,int>
  4. #define pll pair <long long,long long>
  5. #define sc scanf
  6. #define pf printf
  7. #define Pi 2*acos(0.0)
  8. #define ms(a,b) memset(a, b, sizeof(a))
  9. #define pb(a) push_back(a)
  10. #define MP make_pair
  11. #define db double
  12. #define ll long long
  13. #define EPS 10E-10
  14. #define ff first
  15. #define ss second
  16. #define sqr(x) (x)*(x)
  17. #define D(x) cout<<#x " = "<<(x)<<endl
  18. #define VI vector <int>
  19. #define DBG pf("Hi\n")
  20. #define MOD 1000000007
  21. #define CIN ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  22. #define SZ(a) (int)a.size()
  23. #define pf printf
  24. #define sf(a) scanf("%d",&a)
  25. #define sfl(a) scanf("%lld",&a)
  26. #define sff(a,b) scanf("%d %d",&a,&b)
  27. #define sffl(a,b) scanf("%lld %lld",&a,&b)
  28. #define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
  29. #define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
  30. #define sffff(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
  31. #define sffffl(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
  32. #define sfffff(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
  33. #define sfffffl(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
  34. #define sfc(a) scanf("%c",&a)
  35. #define stlloop(v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
  36. #define loop(i,n) for(int i=0;i<n;i++)
  37. #define loop1(i,n) for(int i=1;i<=n;i++)
  38. #define REP(i,a,b) for(int i=a;i<b;i++)
  39. #define RREP(i,a,b) for(int i=a;i>=b;i--)
  40. #define TEST_CASE(t) for(int z=1;z<=t;z++)
  41. #define PRINT_CASE printf("Case %d:\n",z)
  42. #define CASE_PRINT cout<<"Case "<<z<<": "
  43. #define all(a) a.begin(),a.end()
  44. #define intlim 2147483648
  45. #define infinity (1<<28)
  46. #define ull unsigned long long
  47. #define gcd(a, b) __gcd(a, b)
  48. #define lcm(a, b) ((a)*((b)/gcd(a,b)))
  49.  
  50. using namespace std;
  51.  
  52. template<class T1> void deb(T1 e1)
  53. {
  54. cout<<e1<<endl;
  55. }
  56.  
  57. template<class T1,class T2> void deb(T1 e1,T2 e2)
  58. {
  59. cout<<e1<<" "<<e2<<endl;
  60. }
  61. template<class T1,class T2,class T3> void deb(T1 e1,T2 e2,T3 e3)
  62. {
  63. cout<<e1<<" "<<e2<<" "<<e3<<endl;
  64. }
  65. template<class T1,class T2,class T3,class T4> void deb(T1 e1,T2 e2,T3 e3,T4 e4)
  66. {
  67. cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<endl;
  68. }
  69. template<class T1,class T2,class T3,class T4,class T5> void deb(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5)
  70. {
  71. cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<endl;
  72. }
  73. template<class T1,class T2,class T3,class T4,class T5,class T6> void deb(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5,T6 e6)
  74. {
  75. cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<" "<<e6<<endl;
  76. }
  77.  
  78. /*----------------------Graph Moves----------------*/
  79. //const int fx[]={+1,-1,+0,+0};
  80. //const int fy[]={+0,+0,+1,-1};
  81. //const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
  82. //const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
  83. //const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
  84. //const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
  85. /*------------------------------------------------*/
  86.  
  87. /*-----------------------Bitmask------------------*/
  88. //int Set(int N,int pos){return N=N (1<<pos);}
  89. //int reset(int N,int pos){return N= N & ~(1<<pos);}
  90. //bool check(int N,int pos){return (bool)(N & (1<<pos));}
  91. /*------------------------------------------------*/
  92. ll dp[1005][1005];
  93. int n;
  94. int ar[1005];
  95.  
  96. ll f(int x, int l)
  97. {
  98. if(x>=n)
  99. {
  100. return 0;
  101. }
  102. if(dp[x][l]!=-1)
  103. {
  104. return dp[x][l];
  105. }
  106. ll y=f(x+1,l);
  107. for(int i=x+1;i<n;i++)
  108. {
  109. if(ar[x]<ar[i] && ar[i]-ar[x]>=l)
  110. {
  111. y= max(y, ar[i]-ar[x]+f(i+1,ar[i]-ar[x]));
  112. }
  113. }
  114. return dp[x][l]=y;
  115.  
  116. }
  117. int main()
  118. {
  119.  
  120. int t;
  121. sf(t);
  122. while(t--)
  123. {
  124. sf(n);
  125. for(int i=0;i<n;i++){
  126.  
  127. sf(ar[i]);
  128.  
  129. }
  130. ms(dp,-1);
  131. cout<<f(0,0)<<endl;
  132.  
  133. }
  134.  
  135. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement