题解 P1108 【低价购买】

xzyxzy

2017-07-11 20:59:35

Solution

这是一道很坑的题 不会判重,于是乎在书上找到了,照着打了一遍,发现RE了 啊啊啊**数组越界了** 于是乎改啊改,终于过了 其实难点只有两个 一个是常规的动归——**记录最长下降子序列长度** 这个就不详细讲解了,是最基础的动归 第二个嘛,,呵呵——**方案计数** 在草稿纸上打表可知,方案数可以单独弄出一个数组,然后进行运算,当遇到比当前更优的解时,延续那个解的方案数、 当遇到与以前一样优的解时,将那个解的方案数加到q[i]里 那么,,呵呵——**判重** 于是乎书上告诉我用一个bool数组,下标表示其已得到解的数值大小,用1来表示它用到过,避免下次再用 可是啊,,粗心的书没有看到数据范围可是到了**2147483648**啊/已哭晕在厕所/ RE了又RE,总算想到了个好办法:将搜到的值存在一个数组里,顺带一个整数指向它的存储位置,这样每次搜到最优解就讲它的存储位置初始化到1,再判断时就用一个check函数,也优化了原来的时间 ps: register是什么不用管它 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; int n; inline int read() { char ch=getchar(); while(ch>'9'||ch<'0') ch=getchar(); register int h=0; while(ch>='0'&&ch<='9') { h=h*10+ch-48; ch=getchar(); } return h; } int a[5012];//记录数值 int lon[5012];//记录队列长度 int q[5012];//记录前驱元素数量 int b[5012];//避免重复 int t=0; int check(int a) { for(int i=1;i<=t;i++) if(b[i]==a) return 0; return 1; } int main() { n=read(); for(register int i=1;i<=n;i++) a[i]=read(); for(register int i=1;i<=n;i++) lon[i]=1; for(register int i=1;i<=n;i++) q[i]=1; for(register int i=2;i<=n+1;i++)//从2开始是因为不会执行i等于1的情况,到n+1结束是因为为了方便统计所有这一串费用的方案次数之和 { register int maxlon=0; for(register int w=i-1;w>=1;w--) { if(a[w]>a[i]&&lon[w]>maxlon)//如果下降了而且长度长 { maxlon=lon[w]; t=0; b[++t]=a[w]; q[i]=q[w]; } else if(a[w]>a[i]&&lon[w]==maxlon&&check(a[w])==1) { q[i]+=q[w]; b[++t]=a[w]; } } lon[i]=maxlon+1; } cout<<lon[n+1]-1<<" "<<q[n+1]; return 0; } ```