题解 P1108 【低价购买】
xzyxzy
2017-07-11 20:59:35
这是一道很坑的题
不会判重,于是乎在书上找到了,照着打了一遍,发现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;
}
```