题解 P2687 【[USACO4.3]逢低吸纳Buy Low, Buy Lower 】
「QQ红包」
2017-10-09 16:51:32
题解by:redbag
求最长下降子序列
因为n不超过5000，所以O(n^2)复杂度可以接受。
那么我们就可以按照平时求最长单调递减子序列的方法，在求的时候加上一个辅助数组c[i]记录从开始到第i个位置，单调递减子序列为dp[i]时的方案数。
然而,所有的加法都要用高精度
```cpp
/*
ID: ylx14271
PROG: buylow
LANG: C++
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
int a[5010];//每个数
int f[5010];//最长不下降子序列
int c[5010][100];//统计
int lc[5010];
int sum[100];
int d[100],l,ls;
int ans;
int n;
int i,j,k;
using namespace std;
void add(int x)//高精加
{
ls=max(lc[x],ls);
ls++;
for (j=1;j<=ls;j++)
{
sum[j+1]=sum[j+1]+(sum[j]+c[x][j])/10;
sum[j]=(sum[j]+c[x][j])%10;
}
if (sum[ls]==0) ls--;
}
void add1(int x,int y)//高精加 c[x]=c[x]+c[y]
{
lc[x]=max(lc[x],lc[y])+1;
for (k=1;k<=lc[x];k++)
{
c[x][k+1]=c[x][k+1]+(c[x][k]+c[y][k])/10;
c[x][k]=(c[x][k]+c[y][k])%10;
}
if (c[x][lc[x]]==0) lc[x]--;
}
int main()
{
freopen("buylow.in","r",stdin);
freopen("buylow.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&a[i]);
f[i]=0;
lc[i]=1;//长度
c[i][1]=1;
for (j=i-1;j>=1;j--)
{
if (a[j]>a[i])
{
if (f[j]>f[i])
{
f[i]=f[j];//求最长下降子序列长度
//以下相当于c[i]=c[j];长度一样直接赋上去
memset(c[i],0,sizeof(c[i]));//一定要清0
lc[i]=lc[j];
for (k=1;k<=lc[i];k++)
{
c[i][k]=c[j][k];
}
} else if(f[j]==f[i])
{//长度一样方案数就加上
//以下相当于 c[i]+=c[j];
add1(i,j);
}
} else
{
if (a[i]==a[j])//a[i]与a[j]相等，形成的序列相同，就不管了
{//用第i个位置上的数字替换第j个位置上的数字，形成的序列完全相同
if (f[i]==0)
{
//以下相当于c[i]=0;
lc[i]=1;
c[i][1]=0;
}
break;
}
}
}
f[i]++;
ans=max(ans,f[i]);
}
for (i=1;i<=n;i++)
{
if (f[i]==ans)//其实这一句就是if (f[i]==ans) sum+=c[i];要用高精度
{
memset(d,0,sizeof(d));
l=0;
add(i);
}
}
printf("%d ",ans);
int flag=0;
for (i=ls+1;i>=1;i--)//高精度输出
{
if (flag==1) printf("%d",sum[i]); else
if (sum[i]!=0) flag=1,printf("%d",sum[i]);
}
if (flag==0) printf("0");
printf("\n");
return 0;
}
```
当然不带高精度的看着爽点.
当然会wa,但是方法没错.
然而直接复制不带高精度的代码,就说我题解错了的.
那我还是不放了.