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

## 感觉很清晰了，可是为什么一直wa?帮忙看看

Posted by yxysdcl at 2008-03-05 08:32:59 on Problem 1952
```#include <stdio.h>
#include <memory.h>
#define MAX 5010
int price[MAX],dp[MAX];
int count[MAX];
bool on[65536];

void DPLIS(int n)
{
int i,j,max=0;
__int64 sum;
for(i=1;i<n;i++)
{
for(j=i-1;j>=0;j--)
{
if(price[i]<price[j]&&dp[i]<dp[j]+1)
dp[i]=dp[j]+1;
if(max<dp[i])max=dp[i];
}
}
for(i=0;i<n;i++)
{
if(dp[i]==1)
count[i]=1;
else{
memset(on,false,sizeof(on));
for(j=i-1;j>=0;j--)
{
if((dp[i]==dp[j]+1)&&on[price[j]]==false&&price[i]<price[j])
{
count[i]+=count[j];
on[price[j]]=true;
}
}
}
}
memset(on,false,sizeof(on));
sum=0;
for(i=n-1;i>=0;i--)
{
if(dp[i]==max&&on[price[i]]==false)
{
sum+=count[i];
on[price[i]]=true;
}
}
printf("%d %d\n",max,sum);
}

int main()
{
int i,n;
//freopen("in.txt","r",stdin);
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&price[i]);
count[i]=0;
dp[i]=1;
}
DPLIS(n);
}

```

Followed by: