学步园

/*<br /> ID: majunch2<br /> LANG: C++<br /> PROG: buylow<br /> */<br /> //usaco 4.3<br /> //很经典的O(nlogn)LIS问题，还可以求序列方案数</p> <p>#include <cstdio><br /> #include <cstdlib><br /> #include <cstring><br /> //#include <cmath><br /> #include <algorithm><br /> //#include <ctime><br /> using namespace std;<br /> const double inf = 1e15;</p> <p>int p[5010],f[5010]; //p[i]为值，f[i]为以第i元素为末元素的最长上升子序列长度<br /> int best[5010]; //best[i]表示长度为i的序列的当前最小末元素<br /> int num[5010]; //num[i]表示以第i元素为末元素的最长上升子序列方案数</p> <p>int find(int l,int r,int key)<br /> {<br /> int mid;<br /> while (1)<br /> {<br /> mid=(l+r)>>1;<br /> if (best[mid]<key && key<=best[mid+1])<br /> return mid+1;<br /> if (best[mid-1]<key && key<=best[mid])<br /> return mid;<br /> if ( key<best[mid] )<br /> r=mid-1;<br /> else l=mid+1;<br /> }<br /> }</p> <p>int main()<br /> {<br /> //freopen("buylow.in","r",stdin);<br /> //freopen("buylow.out","w",stdout);<br /> int n;<br /> scanf("%d",&n);<br /> for (int i=n;i>=1;i--)<br /> scanf("%d",&p[i]);<br /> memset(best,-1,sizeof(best));<br /> int k;<br /> int ans=1;<br /> best[1]=p[1];f[1]=1;<br /> for (int i=2;i<=n;i++)<br /> {<br /> if (p[i]<=best[1]) k=1; //这里寻k值要很小心，不然容易死循环<br /> else if (p[i]>best[ans]) k=++ans;<br /> else k=find(1,ans,p[i]);</p> <p> best[k]=p[i];<br /> f[i]=k;<br /> }<br /> printf("%d ",ans);</p> <p> //如果相同的序列只能算一种方案，那需要判重，最简单的就是用bool数组了，但由于序列的特性，这里只使用now同样可以<br /> for (int i=1;i<=n;i++)<br /> {<br /> if (f[i]==1) { num[i][0]=num[i][1]=1; continue; }<br /> int now=-1;<br /> for (int j=i-1;j>=1;j--)<br /> if (f[j]+1==f[i] && p[j]<p[i] && now!=p[j])<br /> {<br /> num[i]+=num[j];<br /> now=p[j]; //这里值得思考一下，很简单，对于符合条件的<br /> } //重复的两个数（假设为p[i1]=p[i2])肯定是连续枚举的，因为如果中<br /> } //还枚举了其他数(假设有p[j])那会矛盾。<br /> //若p[j]>p[i1],就有f[j]至少为f[i1]+1，不符合枚举条件；<br /> //若p[j]<p[i1],就有f[i2]至少为f[j]+1,这样p[i2]不会枚举到，矛盾。</p> <p> int now=-1;<br /> int sum=0;<br /> for (int i=1;i<=n;i++)<br /> if (f[i]==ans && now!=p[i])<br /> {<br /> sum+=num[i];<br /> now=p[i];<br /> }<br /> printf("%d/n",sum);</p> <p> return 0;<br /> }</p> <p>