Usaco 4.3.1 Buy Low,Buy Lower詳細解題報告

Usaco 4.3.1
Buy Low, Buy Lower
Byウサギがそろっている
説明
「低吸収」は株を売る成功の秘訣だ.成功した投資家になりたいなら、この秘訣を守らなければなりません.
「低吸いになると、低ければ低いほど買う」
あなたが株を買うたびに、前回購入した時の株価より低くなければなりません.このルールに従って株を買う回数が多ければ多いほどいいので、このルールで何回買えるか見てみましょう.
連続したN日間の毎日の株価を与える.いつでも1日に1回株を買うことができますが、購入時の株価は前回購入した時の株価より低くなければなりません.プログラムを書いて、最大何回株を買うことができるかを求めます.
次の表を例にとると、ある数日の株価は:

   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回まで株を買うことができる.1つの買い方は以下の通りです(他の買い方があるかもしれません):

   2  5  6  10

   69 68 64 62

書式設定
PROGRAM NAME: buylow
INPUT FORMAT:
(file buylow.in)
1行目:N(1<=N<=5000)は、株が買える日数を表します.
2行目以下:N個の正の整数(複数行に分割可能)、i個目の正の整数はi日目の株価を表す.これらの正の整数の大きさはlongint/long(c++)を超えない.
OUTPUT FORMAT:
(file buylow.out)
1行のみで、2つの整数を出力します.
株式を購入できる日数がこの値に達する株式購入案の数
シナリオの数を計算する際、2つのシナリオの株価シーケンスが同じであれば、このような2つのシナリオは同じとみなされます(1つのシナリオしか計算できません).したがって、2つの異なる日数シーケンスが同じ株価シーケンスを生成する可能性があります.これにより、1回しか計算できません.
SAMPLE INPUT

12

68 69 54 64 68 64 70 67

78 62 98 87

SAMPLE OUTPUT

4 2

 
分析:
1)第一問,最大降下サブシーケンス,古典dp,これはあまり言わないが,知らないまま「最大降下(上昇)サブシーケンス」を検索する
2)第2問では,最大降下長のシーケンスの種類を問い,単語が全く同じ重複計算を行わない.これはちょっと面倒です.
1.この問題に対して、配列num[N],num[i]を開き、i番目の位置を記録する前に、dp[i]の長さ(i番目のビットで終わる最長降下シーケンスの長さを表す)に対応するシーケンスの種類数を指定することもできる.例:
オリジナル
1
16
17
18
20
10
22
22
8
17
26
14
3
24
8
1
2
21
2
17
dp
1
1
1
1
1
2
1
1
3
2
1
3
4
2
4
5
5
3
5
4
Num
1
1
1
1
1
4
1
1
4
3
1
3
7
1
3
10
10
1
10
1
                    
2.num[i]はどのように更新されましたか?dp[j]=dp[i]-1を満たすすべてのj(j、すなわち、合法的なシーケンスの前駆者の1人)のnum[j]の和を加算するべきである.ただし、シーケンスが重複している可能性がある問題に注意してください.たとえば、次のようにします.
9 8 7 6 2 6 5
1番目に出現した6および2番目の6は、対応する減算シーケンスが9 8 7 6であり、繰り返しに属する.このとき、現在dp[i]==dp[j]+1(jすなわち、合法シーケンスの前駆者の1人)num[j]が統計されているかどうかを記録する.
3.もう一つ質問があります.前駆位の2つの同じ数に出会って、勝手に1人を取りますか?こだわりはありますか?
もちろん!例:
オリジナル
9
7
5
8
5
1
Dp
1
2
3
2
3
4
Num
1
1
1
1
2
2
 
最初に現れた5と2番目の5について、彼らのdpは同じだがnumは違うことに気づいただろう.ここで最後の5を取ることができます.理由は次のとおりです.
最後の5以外のシーケンスについては、最後の5は、必ず取得できます.例えば、第2の5について、第1の5の9 7 5シーケンスについて、第2の5も同様に取得することができる.さらに、上記の例の2番目の5のような、後の5の方がより多くの取り方をする可能性があり、9 8 5というシーケンスも得ることができる.だからここで、最後の1に対応するnumは2であるべきです.
 
3.実装方法:このような状況に鑑みて、私たちは後ろから前へ検索し、visited[]を記録することができ、アクセスしたことは累積したことを示し、前に同じものが現れたら無視する.正確性を保証できる
 
 
3)詳細については、
1.シーケンスの末尾に0を追加することができ、最大長が複数ある場合の合計数を統計するのに便利です.
2.この問題は高精度を要求する.数が大きすぎて、私のコードは以前書いた高精度テンプレートを使って、比較的に肥大化しているかもしれません.ほほほ
 
 
コード:
//コアコードはmain関数の中にあります.前の大きな部分は高精度テンプレートです.無視してください.
/* ID:dingyag1 LANG:C++ TASK:buylow */#include #include #include #include using namespace std; void func_add(vector ∑,vector a,int n) { vector::size_type i; for(i=0;isum.size()) sum.insert(sum.end(),i+n+1-sum.size(),0); sum[i+n]+=a[i]; }//cout<<「出力add関数中sum:」<=10000) { if(i==sum.size()-1) sum.push_back(0); sum[i+1]+=sum[i]/10000; sum[i]=sum[i]%10000; } } } vector & operator +=(vector &a,const vector &b ) { func_add(a,b,0); return a; } void mitoa(int a,char *s,int c) { int n,i=0; char s2[10]; do { s2[i++]=a%c+'0'; a=a/c; }while(a>0); for(n=0;n ∑,int nlog) { vector::size_type i; string s; int tmp; bool f=0; char ss[10]={0}; for (i=0;i1){//中間for(i=sum.size()−2;i>0;i−){if(sum[i]<10){s+="000";}else if(sum[i]<100) { s+="00"; } else if(sum[i]<1000) { s+="0"; } mitoa(sum[i],ss,10); s+=ss; }//取尾if(sum[0]<10){s+="000";}else if(sum[0]<100) { s+="00"; } else if(sum[0]<1000) { s+="0"; } mitoa(sum[0],ss,10); s+=ss; }//小数点tmp=s.size()を処理する.if(nlog==0) { } else if(nlog>0) { s.append(nlog,'0'); } else if(nlog>-tmp) { s.insert(tmp+nlog,1,'.'); i=s.find_last_not_of('0'); s.erase(i+1,s.size()-i-1); if(s[s.size()-1]=='.') s.erase(s.size()-1,1); } else { s.insert((string::size_type)0,-(tmp+nlog),'0'); s.insert((string::size_type)0,"0."); i=s.find_last_not_of('0'); s.erase(i+1,s.size()-i-1); if(s[s.size()-1]=='.') s.erase(s.size()-1,1); }//前の0 i=s.find_を削除first_not_of('0'); s.erase(0,i); cout<<""<>s; } } int main() { freopen("buylow.in","r",stdin); freopen("buylow.out","w",stdout); int N,S[5003],dp[5003]={0}; int i,j,max=1,maxp; vector num[5003]; cin>>N; for(i=1;i<=N;++i){cin>>S[i];dp[i]=1;//初期化dpは1 num[i].push_back(1);//////////////////末尾+0はN++を統計するのに便利である.S[N]=0;num[N].push_back(1);dp[N]=1;///if (N==1) { maxp=1; } for (i=2;i<=N;++i) { bool visited[50001]={0}; for (j=i-1;j>0;--j) { if (S[j]>S[i] && dp[j]+1>=dp[i]) { if (dp[j]+1>dp[i]) { dp[i]=dp[j]+1; num[i]=num[j]; if (dp[i]>max) { max=dp[i]; maxp=i; }//record }else if (dp[i]==dp[j]+1) { if (!visited[S[j]]) { num[i]+=num[j]; }else {//num[i]+=num[j]; } } visited[S[j]]=1; } } } if (max==1) { cout<<1<<""<