(미해결) buy lower 더블릿

#include <stdio.h>

#include <algorithm>

#include <vector>

using namespace std;

int dp[5005] = { 0 };

int arr[5005] = { 0 };

vector<vector<int> > par(5005);

int sum = 0, tmp = 1,maxDp=0;

void findPar(int x,int tmp, int time) {

if (time == maxDp) {

sum += tmp;

return;

}

for (int i = 0; i < par[x].size(); i++)

findPar(par[x][i],tmp,time+1);

}

int main() {

int n;

scanf("%d", &n);

for (int i = 1; i <= n; i++) {

scanf("%d", &arr[i]);

}

dp[1] = 1;

for (int i = 2; i <= n; i++) {

int maxNum = 0;

for (int j = 1; j < i; j++) {

if (arr[j] > arr[i] && maxNum < dp[j]) {

maxNum = dp[j];

}

}

dp[i] = maxNum + 1;

for (int j = 1; j < i; j++) {

if (arr[j] > arr[i] && dp[j] == maxNum) {

par[i].push_back(j);

}

}

}

for (int i = 1; i <= n; i++) {

maxDp = max(maxDp, dp[i]);

}

for (int i = 1; i <= n; i++)

printf("%d ", dp[i]);

for (int i = n; i >=1; i--) {

printf("%d->", arr[i]);

for (int j = 0; j < par[i].size(); j++)

printf("%d ", arr[par[i][j]]);

printf("\n");

}

for (int i = 1; i <= n; i++) {

if (maxDp == dp[i]) {

findPar(i, 1, 1);

printf("a%d", arr[i]);

}

}

printf("%d %d", maxDp, sum);

}