POJ 1952 C++:BUY LOW, BUY LOWER

2017-01-03 19:13:47来源:CSDN作者:u010203544人点击

思路:

1. 用两个数组分别存长度和方法数(动态规划)2. 找到第一个比i大的数,将已i结尾的长度和方法数赋值3. 如果又找到一个比i大的数,长度正好为i-1,那么就更新i的方法数4. 如果找到一个数和i相等,并且此时i的长度还是初始化的1,那么将i的方法数置为0,并且break
#include <stdio.h>#include <iostream>using namespace std;int n;int a[5005];int dp[5005];int num[5005];int main(){	cin>>n;	int i;	for(i=0;i<n;i++){		scanf("%d",&a[i]);		dp[i]=1;		num[i]=1;	}	int j;	for(i=1;i<n;i++){		for(j=i-1;j>=0;j--){			if(a[j]>a[i]){				if(dp[j]+1>dp[i]){					dp[i]=dp[j]+1;					num[i]=num[j];				}				else if(dp[j]+1==dp[i]){					num[i]+=num[j];				}			}			else if(a[j]==a[i]){				if(dp[i]==1)num[i]=0;				break;			}		}	}	int maxlen=0;	for(i=0;i<n;i++){        if(dp[i]>maxlen)maxlen=dp[i];	}	int maxsum=0;	for(i=0;i<n;i++){		if(dp[i]==maxlen)maxsum+=num[i];	}	cout<<maxlen<<' '<<maxsum<<endl;		return 0;}


最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台