Advertisement
Guest User

Untitled

a guest
Apr 26th, 2019
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.77 KB | None | 0 0
  1. #include <stdio.h>
  2.  
  3. int W[1001], S[1001];
  4. int n;
  5. int next[1001];
  6.  
  7. int memo[1001];
  8.  
  9. int bt(int first) {
  10. if (memo[first] != -1)
  11. return memo[first];
  12.  
  13. int maxSeq = 1;
  14. next[first] = first;
  15.  
  16. for(int i=0; i<n; i++) {
  17. if(W[i]>W[first] && S[i]<S[first]) {
  18. int aux = bt(i) + 1;
  19. if(aux>maxSeq) {
  20. maxSeq=aux;
  21. next[first] = i;
  22. }
  23. }
  24. }
  25.  
  26. memo[first] = maxSeq;
  27. return maxSeq;
  28. }
  29.  
  30. int main() {
  31.  
  32. n = 0;
  33. while( scanf("%d %d", &W[n], &S[n])!= EOF ) {
  34. n++;
  35. }
  36.  
  37. for (int i = 0; i < 1001; ++i){
  38. memo[i] = -1;
  39. }
  40.  
  41. int maxSeq = bt(0);
  42. int best = 0;
  43. for(int i=1; i<n; i++) {
  44. int aux = bt(i);
  45. if(aux>maxSeq) {
  46. maxSeq=aux;
  47. best = i;
  48. }
  49. }
  50. printf("%d\n", maxSeq);
  51. while(1) {
  52. printf("%d\n", best+1);
  53. if(next[best]==best) break;
  54. best = next[best];
  55. }
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement