usaco 4.3.1 buy low,buy lower
首先这题的第一问是很简单的,学过dp的应该就不会有问题了,虽然有O(n*lgn)的算法,但是这里还是用O(n^2)的比较好一点,因为还有第二问,对于第二问我是这么想的,用如下序列来说明,9 8 7 10 9 7 我在原序列之后加上一个0,这样的话只需要得到最后这个0的信息就是我们要求的值了.我们可以用ans表示每一个数据的最大下降子序列的长度,另外用num表示原数据,f表示方案数,最后还有一个数组used表示是否在算f时这个值已经用过[这里的值是原数据]然后可以得到上面的数据的一些信息如下
num 9 8 7 10 9 7
ans 1 2 3 1 2 3
f 1 1 1 1 1 2
这里我们没有用到used数组,但是待会的程序中就有用了,首先我们可以得到所有的ans值,然后这里的f我们是根据前面的某些值得到的,如果ans[j]+1>ansi那么f[i]就由f[j]得来,但是可能有多个这样的情况:ans[j]+1==ansi这里怎么解决呢?这里我们会发现如果对这些j中,如果某两个j对应的num值不同的话,那么f[i]肯定就是这两个f值的和,因为他们产生的序列肯定是不会一样的,但是如果某两个j对应的num相同的话,我们怎么办呢?这里我们只需考虑后面那个j就行了,因为后面那个j会覆盖前面那个j的所有信息,假设后面那个j的下标是j1后面那个是j2那么ans[j2]>=ans[j1]肯定成立,同时f[j2]>=f[j1]也成立,这里很明显吧,因为我们如果把j1到j2中间的那些数据去掉的话那么就是取相等的,如果中间再加入一个数到下降子序列里面的话,那么就是取>了.理解了这些之后我们可以得到如下的代码 for i=1 i <= n;i++ for j=i-1;j>=0;j– if num[j] > num[i] if ans[j]+1 > ans[i] ans[i]=ans[j]+1; f[i]=f[j]; memset(num,0,sizeof(num)); used[num[j]]=1;//这里就用到了上面的只取后面那个,因为后面这个已经把前面那个的信息给覆盖了 else if ans[j]+1 == ans[i] & 0 == used[num[j]] f[i] += f[j]; used[num[j]]=1; 这样之后输出的答案就是ans[n]-1和f[n]了,不过这里得用高精度具体代码如下:
ID:qcx97811
LANG:C
PROG:buylow
/
#include
#include
#include
int N;
int ans[5006],num[5006],front[5006][100];
int used[20006];
void add(int a[],int b[])
{//高精度加法 结果存在a数组中
int len,i
if(a[0] > b[0])
len = a[0];
else
len = b[0];
for(i = a[0]+1i < 100;i++)
a[i]=0//清0后面的数据
for(i = b[0]+1i < 100;i++)
b[i]=0//清0后面的数据
for(i = 1i <= len;i++)
{
a[i] += b[i];
a[i+1] += a[i]/10
a[i] %= 10
}
if(0 != a[len+1])
a[0] = len+1
else
a[0] = len
return
}
int main(void)
{
freopen(“buylow.in”,“r”,stdin);
freopen(“buylow.out”,“w”,stdout);
int i,j,k
int len
scanf(“%d”,N);
for(i = 0i < N;i++)
{
scanf(“%d”,num[i]);
}
num[N]=0
ans[0] = 1
front[0][0] = 1
front[0][1] = 1
for(i = 1i <= N;i++)
{
ans[i] = 1
memset(front[i],0,sizeof(front[i]));
memset(used,0,sizeof(used));
for(j = i-1j >;= 0;j–)
{
if(num[j] > num[i])
{
if(ans[i]<ans[j]+1)
{
ans[i] = ans[j]+1
for(k = 0k <= front[j][0];k++)
{
front[i][k] = front[j][k];
}
for(k = front[i][0]+1k < 100;k++)
front[i][k]=0
memset(used,0,sizeof(used));
used[num[j]]=1
}
else
{
if((ans[j]+1==ans[i]) & (0 == used[num[j]]))
{
add(front[i],front[j]);
used[num[j]]=1
}
}
}
}
if(0 == front[i][0])
{
front[i][1]=1
front[i][0]=1
}
}
printf(“%d “,ans[N]-1);
for(i = front[N][0];i >= 1;i–)
printf(“%d”,front[N][i]);
printf(“\n“);
return 0
}
