Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- int W[1001], S[1001];
- int n;
- int next[1001];
- int memo[1001];
- int bt(int first) {
- if (memo[first] != -1)
- return memo[first];
- int maxSeq = 1;
- next[first] = first;
- for(int i=0; i<n; i++) {
- if(W[i]>W[first] && S[i]<S[first]) {
- int aux = bt(i) + 1;
- if(aux>maxSeq) {
- maxSeq=aux;
- next[first] = i;
- }
- }
- }
- memo[first] = maxSeq;
- return maxSeq;
- }
- int main() {
- n = 0;
- while( scanf("%d %d", &W[n], &S[n])!= EOF ) {
- n++;
- }
- for (int i = 0; i < 1001; ++i){
- memo[i] = -1;
- }
- int maxSeq = bt(0);
- int best = 0;
- for(int i=1; i<n; i++) {
- int aux = bt(i);
- if(aux>maxSeq) {
- maxSeq=aux;
- best = i;
- }
- }
- printf("%d\n", maxSeq);
- while(1) {
- printf("%d\n", best+1);
- if(next[best]==best) break;
- best = next[best];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement