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

## DP再DP，不知道哪里错啦，帮忙看看

Posted by mingruoyuan at 2009-07-02 16:52:53 on Problem 1952
```#include<stdio.h>
int k,max,n,a[5001],s[5001],num[5001],sum=0;
int main()
{
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
s[1]=1;
for(i=2;i<=n;i++)
{
s[i]=1;
for(j=i-1;j>0;j--)
if(a[j]>a[i]&&s[j]>=s[i])
s[i]=s[j]+1;
}//动态规划，s[i]表示第i个数a[i]在递减子序列中可以排到的最大位置在第s[i]个位置
max=s[n];
for(i=1;i<n;i++)
if(max<s[i]) max=s[i];//max就是最大长度
for(i=1;i<=n;i++)
{
k=-10;//用k排除相同的序列
if(s[i]==1)
{
num[i]=1;
continue;
}
for(j=1;j<i;j++)
if(a[j]>a[i]&&s[j]+1==s[i]&&a[j]!=k)
{
k=a[j];
num[i]+=num[j];
}
}//num[i]表示以第i个数a[i]结尾的不同的长为s[i]的序列；
k=-10;
for(i=1;i<=n;i++)
if(s[i]==max&&a[i]!=k)
{
k=a[i];
sum+=num[i];
}
printf("%d %d\n",max,sum);
return 0;
}

if(a[x]>a[j]&&s[x]==s[i]) s[j]=s[x]+1=s[i]+1;

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator