Posted on 2008-08-08 16:45
Hero 阅读(131)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
/*
ID: wangzha4
LANG: C++
TASK: buylow
Test 1: TEST OK [0.000 secs, 4788 KB]
Test 2: TEST OK [0.000 secs, 4792 KB]
Test 3: TEST OK [0.022 secs, 4788 KB]
Test 4: TEST OK [0.011 secs, 4788 KB]
Test 5: TEST OK [0.011 secs, 4788 KB]
Test 6: TEST OK [0.011 secs, 4792 KB]
Test 7: TEST OK [0.032 secs, 4788 KB]
Test 8: TEST OK [0.011 secs, 4788 KB]
Test 9: TEST OK [0.076 secs, 4792 KB]
Test 10: TEST OK [0.346 secs, 4788 KB]
*/
//高精度 + DP
//在data[]的最后面加一个0--data[++inn] = 0 ;
//在统计个数的时候用来next[i]来保存在i后面且和i相等的数据的位置
//data[i] = data[next[i]] -- if( next[i]!=0 )
//if( next[j] && next[j]<i ) continue ;
//这样就避免了重复统计
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <ctype.h>
#include <iostream>
using namespace std ;
#define llong unsigned long long
#define unint unsigned int
#define printline printf( "\n" )
typedef long long huge ;
const int Base=1000000000;
const int Capacity=100;
const int INF = 1000000 ;
const int size = 5100 ;
struct BigInt{
int Len;
int Data[Capacity];
BigInt():Len(0){}
BigInt(const BigInt &V):Len(V.Len){memcpy(Data,V.Data,Len*sizeof*Data);}
BigInt(int V):Len(0){for(;V>0;V/=Base) Data[Len++]=V%Base;}
BigInt &operator=(const BigInt &V){Len=V.Len;memcpy(Data,V.Data,Len*sizeof*Data);return *this;}
int &operator[](int Index){return Data[Index];}
int operator[](int Index)const{return Data[Index];}
};
typedef struct BigInt BigInt ;
int compare(const BigInt &A,const BigInt &B){
if(A.Len!=B.Len) return A.Len>B.Len ? 1:-1;
int i;
for(i=A.Len-1;i>=0 && A[i]==B[i];i--);
if(i<0)return 0;
return A[i]>B[i] ? 1:-1;
}
BigInt operator+(const BigInt &A,const BigInt &B){
int i,Carry(0);
BigInt R;
for(i=0;i<A.Len||i<B.Len||Carry>0;i++){
if(i<A.Len) Carry+=A[i];
if(i<B.Len) Carry+=B[i];;
R[i]=Carry%Base;
Carry/=Base;
}
R.Len=i;
return R;
}
BigInt operator-(const BigInt &A,const BigInt &B){
int i,Carry(0);
BigInt R;
R.Len=A.Len;
for(i=0;i<R.Len;i++){
R[i]=A[i]-Carry;
if(i<B.Len) R[i]-=B[i];
if(R[i]<0) Carry=1,R[i]+=Base;
else Carry=0;
}
while(R.Len>0&&R[R.Len-1]==0) R.Len--;
return R;
}
BigInt operator*(const BigInt &A,const int &B){
int i;
huge Carry(0);
BigInt R;
for(i=0;i<A.Len||Carry>0;i++){
if(i<A.Len) Carry+=huge(A[i])*B;
R[i]=Carry%Base;
Carry/=Base;
}
R.Len=i;
return R;
}
istream &operator>>(istream &In,BigInt &V){
char Ch;
for(V=0;In>>Ch;){
V=V*10+(Ch-'0');
if(In.peek()<=' ') break;
}
return In;
}
ostream &operator<<(ostream &Out,const BigInt &V){
int i;
Out<<(V.Len==0 ? 0:V[V.Len-1]);
for(i=V.Len-2;i>=0;i--) for(int j=Base/10;j>0;j/=10) Out<<V[i]/j%10;
return Out;
}
int inn ;
int maxlen[size] ;
BigInt maxcnt[size] ;
int next[size] = {0} ;
int data[size] ;
void input()
{
scanf( "%d", &inn ) ;
for( int i=1; i<=inn; i++ ) scanf( "%d", &data[i] ) ;
for( int i=1; i<inn; i++ ) for( int j=i+1; j<=inn; j++ )
if( data[i] == data[j] ) {
next[i] = j ; break ;
}
data[++inn] = 0 ;
}
void DP_process()
{
//BigInt BInt = new BigInt( 1 ) ;//大整数1，用于初始化其他大整数数组
BigInt BInt( 1 ) ;
maxlen[1] = 1 ; maxcnt[1] = BInt ;
for( int i=2; i<=inn; i++ ) {
maxcnt[i] = BInt ; maxlen[i] = 1 ;//DP_init
for( int j=1; j<i; j++ ) {
if( next[j] && next[j] < i ) continue ;//如果可以在i的前面找到data[j]的替代
if( data[j] > data[i] ) {
if( maxlen[j]+1 > maxlen[i] ) {
maxlen[i] = maxlen[j] + 1 ; maxcnt[i] = maxcnt[j] ;
}
else if( maxlen[j]+1 == maxlen[i] ) {
maxcnt[i] = maxcnt[i] + maxcnt[j] ;//加法原理
}
}
}//for( int j )
}//for( int i )
}
void output()
{
printf( "%d ", maxlen[inn]-1 ) ;
cout << maxcnt[inn] << endl ;
}
int main()
{
freopen( "buylow.in", "r", stdin ) ;
freopen( "buylow.out","w",stdout ) ;
input() ;
DP_process() ;
output() ;
return 0 ;
}