Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

今天看了别处的中文描述，发现之前理解题好像也错了，看看了别人的，终于搞出来了，发个code庆祝一下

Posted by dongshanluo at 2011-04-25 23:59:21 on Problem 1952
```#include <stdio.h>
#define N 5010
int n;
int a[N];
int len[N];
int num[N];

int main()
{
int i;
int j;
int maxlen;
int ans;
while(scanf("%d", &n) != EOF) {
for(i = 1; i <= n; i++)scanf("%d", &a[i]);
len[1] = 1;
num[1] = 1;
for(i = 2; i <= n; i++) {
len[i] = 1;
num[i] = 1;
for(j = 1; j < i; j++) {
if(a[j] > a[i] && len[j] + 1 > len[i]) {
len[i] = len[j] + 1;
num[i] = num[j];
} else if(a[j] > a[i] && len[j] +1 == len[i]) {
num[i] += num[j];
}
}
for(j = i - 1; j >= 1; j--) {
//此处，如果发现前边与自己相同的而且最大长度也相同，则把前边那个的最大长度的数目置为0，因为后边的那个一定能覆盖前边那个的所有情况的
if(a[j] == a[i] && len[j] == len[i]) {
num[j] = 0;
break;
}
}
}
maxlen = len[n];ans = num[n];
for(i = n - 1; i >= 1; i--) {
if(len[i] > maxlen) {
maxlen = len[i];ans = num[i];
} else if(len[i] == maxlen) ans += num[i];
}
printf("%d %d\n", maxlen, ans);
}
return 0;
}```

Followed by: