Buy Low, Buy Lower
The advice to "buy low" is half the formula to success in the stock market. But to be considered a great investor you must also follow this problems' advice:
"Buy low, buy lower"
That is, each time you buy a stock, you must purchase more at a lower price than the previous time you bought it. The more times you buy at a lower price than before, the better! Your goal is to see how many times you can continue purchasing at ever lower prices.
You will be given the daily selling prices of a stock over a period of time. You can choose to buy stock on any of the days. Each time you choose to buy, the price must be lower than the previous time you bought stock. Write a program which identifies which days you should buy stock in order to maximize the number of times you buy.
By way of example, suppose on successive days stock is selling like this:
Day 1 2 3 4 5 6 7 8 9 10 11 12
Price 68 69 54 64 68 64 70 67 78 62 98 87
In the example above, the best investor (by this problem, anyway) can buy at most four times if they purchase at a lower price each time. One four day sequence (there might be others) of acceptable buys is:
Day 2 5 6 10
Price 69 68 64 62
PROGRAM NAME: buylow
INPUT FORMAT
Line 1: N (1 <= N <= 5000), the number of days for which stock prices are available.
Line 2..etc: A series of N positive space-separated integers (which may require more than one line of data) that tell the price for that day. The integers will fit into 32 bits quite nicely.
SAMPLE INPUT (file buylow.in)
12
68 69 54 64 68 64 70 67
78 62 98 87
OUTPUT FORMAT
Two integers on a single line:
the length of the longest sequence of decreasing prices
the number of sequences that have this length
In counting the number of solutions, two potential solutions are considered the same (and would only count as one solution) if they repeat the same string of decreasing prices, that is, if they "look the same" when the successive prices are compared. Thus, two different sequence of "buy" days could produce the same string of decreasing prices and be counted as only a single solution.
SAMPLE OUTPUT (file buylow.out)
4 2
-----------------------------------------------------------
求最长递减子序列。
参考算法：http://blog.pfan.cn/rickone/13086.html
上述算法是求最长递增子序列，而且只需要求长度，并不需要求数量。
因此需要添加一个数组记录每一个长度对应的数目。
此外，某个长度可能是一个非常大的整数。因此需要定义一个整数类：
class big{
public :
int s[bit];
big operator+ (big &b){
}
big & operator =(const big &a)
big & operator =(const int a)
friend ostream & operator <<(ostream & input,big & b)
};
我所遇到的testcase8就有这么长：1606938044258990275541962092341162602522202993782792835301376
USER: Ma yunlei [yunleis2]
TASK: buylow
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.000 secs, 3328 KB]
Test 2: TEST OK [0.000 secs, 3328 KB]
Test 3: TEST OK [0.000 secs, 3328 KB]
Test 4: TEST OK [0.000 secs, 3328 KB]
Test 5: TEST OK [0.000 secs, 3328 KB]
Test 6: TEST OK [0.000 secs, 3328 KB]
Test 7: TEST OK [0.000 secs, 3328 KB]
Test 8: TEST OK [0.000 secs, 3328 KB]
Test 9: TEST OK [0.054 secs, 3328 KB]
Test 10: TEST OK [0.189 secs, 3328 KB]
------------------------------------------------------------------
/*
ID:yunleis2
PROG:buylow
LANG:C++
*/
#include<iostream>
#include<fstream>
#include<cmath>
#include<iomanip>
using namespace std;
const int maxn=5001;
const int base=1000000;
const int bit=13;
class big{
public :
int s[bit];
big operator+ (big &b){
big bt;
int carry=0;
for(int i=bit-1;i>=0;--i){
bt.s[i]=(s[i]+b.s[i]+carry)%base;
carry=(s[i]+b.s[i]+carry)/base;
}
return bt;
}
big & operator =(const big &a){
for(int i=0;i<bit;++i)
this->s[i]=a.s[i];
return *this;
}
big & operator =(const int a){
for(int i=0;i<bit;++i)
this->s[i]=0;
this->s[bit-1]=a;
return *this;
}
friend ostream & operator <<(ostream & input,big & b){
bool flag=false;
bool flag1=false;
for(int i=0;i<bit;++i)
{
if(b.s[i]!=0)
flag=true;
if(flag){
if(!flag1)
{
input<<b.s[i];
flag1=true;
}
else
input<<setw(6)<<setfill('0')<<b.s[i];
}
}
return input;
}
};
//seq seqs[maxn];
int ptr=0;
int n;
int stock[maxn];
int size[maxn];
big num[maxn];
bool flag[maxn];
int main()
{
fstream fin("buylow.in",ios::in );
fin>>n;
for(int i=0;i<n;++i)
fin>>stock[i];
//seqs[ptr++]
size[0]=1;
num[0]=1;
flag[0]=true;
for(int i=1;i<n;i++){
size[i]=1;
num[i]=1;
flag[i]=true;
for(int j=0;j<i;j++){
if(!flag[j])
continue;
if(stock[i]<stock[j])
{
if(size[j]>size[i]-1)
{
size[i]=size[j]+1;
num[i]=num[j];
}
else if(size[j]==(size[i]-1))
num[i]=num[i]+num[j];
}
else if(stock[i]==stock[j]){
#if 0
if(size[j]==1){
size[i]=0;
num[i]=0;
}
else{
size[i]=1;
num[i]=1;
}
#endif
flag[j]=false;
if(size[j]>size[i])
{
size[i]=size[j];
num[i]=num[j];
}
else if(size[j]==(size[i]))
num[i]=num[j];
}
}
}
int maxlength=0;
big num1;
num1=0;
for(int i=n-1;i>=0;--i){
//cout<<"("<<size[i]<<"~"<<num[i]<<") ";
if(!flag[i])
continue;
if(maxlength<size[i])
{
maxlength=size[i];
num1=num[i];
}
else if(maxlength==size[i])
num1=num1+num[i];
}
//int num2=num1.s[bit-1];
fstream fout("buylow.out",ios::out);
fout<<maxlength<<" ";
fout<<num1<<endl;
//system("pause");
}
