做网站备案谁做,网站建设启凡,wordpress显示特效,公司排名的网站低价购买#xff08;洛谷 1108#xff09;
题目描述
“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者#xff0c;你必须遵循以下的问题建议:“低价购买#xff1b;再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购… 低价购买洛谷 1108
题目描述
“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者你必须遵循以下的问题建议:“低价购买再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(2^16范围内的正整数)你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买再低价购买”的原则。写一个程序计算最大购买次数。
这里是某支股票的价格清单
日期 1 2 3 4 5 6 7 8 9 10 11 12
价格 68 69 54 64 68 64 70 67 78 62 98 87
最优秀的投资者可以购买最多4次股票可行方案中的一种是
日期 2 5 6 10
价格 69 68 64 62
输入输出格式
输入格式 第1行: N (1 N 5000)股票发行天数
第2行: N个数是每天的股票价格。 输出格式 输出文件仅一行包含两个数:最大购买次数和拥有最大购买次数的方案数(2^31)当二种方案“看起来一样”时就是说它们构成的价格队列一样的时候,这2种方案被认为是相同的。 输入输出样例
输入样例#1 BUYLOW.IN
12
68 69 54 64 68 64 70 67 78 62 98 87
输出样例#1 BUYLOW.OUT
4 2
解题方法 就是求最大下降序列最长长度就是前面长度最长的并且大于这个数的序列的长度1个数就是前面所有长度等于这个序列的长度-1并且大于这个数的序列的个数相加在一起记得去重。
代码 strong#includeiostream
#includecstring
using namespace std;
int n,maxs,maxg,a[5001],b[5001],f[5001];
bool t[70000];
int main()
{cinn;for (int i1;in;i)cina[i];for (int i1;in;i){memset(t,true,sizeof(t)); //用于判断这个数用过没有f[i]1; //预处理for (int j1;ji;j)if (a[i]a[j]) f[i]max(f[i],f[j]1); //如果前面的数大于这个数那么当前序列当前序列和第j个数的序列1较大的for (int ji-1;j1;j--) //越后面的个数就越多先用后面的if (t[a[j]] f[j]f[i]-1 a[j]a[i]) //这个数用过没有长度符合吗大于次数吗{b[i]b[i]b[j]; t[a[j]]false; //不能用了 }b[i]max(b[i],1); //如果没有就创一个新的maxsmax(maxs,f[i]); //求最大数}memset(t,true,sizeof(t));for (int in;i1;i--)if (f[i]maxs t[a[i]]) //看看符不符合条件{maxgmaxgb[i];//个数相加t[a[i]]false;}coutmaxs maxg;
}/strong
