题解 P2687 【[USACO4.3]逢低吸纳Buy Low, Buy Lower 】
前言：
这题一开始看不知道要高精，，后面错了一个点十分懵逼，然后方知要高精，但是呢，写字符串高精太累了，细节太多，不想写，而这题已经做了90分了，放弃太可惜了，咋办呢，只好取个折中的办法，自己想一个细节比较少的数组高精。
全题的思路：
求最长下降子序列，
- 从1开始枚举每一天的价格。
- 再从这一天开始往回找每一天到每一天且必须选这天时最长的购买天数，将其加一变成现有这天的最长购买天数。
- 记录并将最长的所有可能种数相加，最后得到到这天的最长购买天数可能种数。
记住初始化每天购买最长天数为1，且可能形成此序列种数。- 判断重复序列并删除。
重头戏：
别人都是字符串高精，double卡高精，可是我不一样，数组高精。
介绍：
数组高精，本人原创，优点，细节少，数组开得小也可以获得正确大数据，简单易学，数据较小可以直接手打加复制（如此题），数据大可用循环，（思想上与字符串高精类似，但是更优）。
描述：
用数组代替字符串，第i个数组可以放置第10000000^（i-1）到10000000^i的数，若一个数组记录的数超过10000000则进位，最后直接各位输出（除第一个有存数的数组外，其他数组需将前导0输出，所以需要各位输出）。
代码如下（不喜勿喷，因为数据较小所以用粘贴来高精，循环也可以）：
#include<bits/stdc++.h>
using namespace std;
long long n,a[5005],dp[5005],ans1;
long long ans2[10],b[1150][5005];
int main() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
dp[i]=1;
b[1][i]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(a[i]<a[j]){
if(dp[i]==dp[j]+1){
b[10][i]=b[10][j];
b[9][i]+=b[9][j];
b[8][i]+=b[8][j];
b[7][i]+=b[7][j];
b[6][i]+=b[6][j];
b[5][i]+=b[5][j];
b[4][i]+=b[4][j];
b[3][i]+=b[3][j];
b[2][i]+=b[2][j];
b[1][i]+=b[1][j];
b[2][i]+=b[1][i]/10000000;
b[1][i]%=10000000;
b[3][i]+=b[2][i]/10000000;
b[2][i]%=10000000;
b[4][i]+=b[3][i]/10000000;
b[3][i]%=10000000;
b[5][i]+=b[4][i]/10000000;
b[4][i]%=10000000;
b[6][i]+=b[5][i]/10000000;
b[5][i]%=10000000;
b[7][i]+=b[6][i]/10000000;
b[6][i]%=10000000;
b[8][i]+=b[7][i]/10000000;
b[7][i]%=10000000;
b[9][i]+=b[8][i]/10000000;
b[8][i]%=10000000;
b[10][i]+=b[9][i]/10000000;
b[9][i]%=10000000;
}
if(dp[i]<dp[j]+1){
dp[i]=dp[j]+1;
b[10][i]=b[10][j];
b[9][i]=b[9][j];
b[8][i]=b[8][j];
b[7][i]=b[7][j];
b[6][i]=b[6][j];
b[5][i]=b[5][j];
b[4][i]=b[4][j];
b[3][i]=b[3][j];
b[2][i]=b[2][j];
b[1][i]=b[1][j];
}
}
}
for(int j=i-1;j>=1;j--){
if(dp[i]==dp[j]&&a[i]==a[j])dp[j]=a[j]=0;
}
ans1=max(ans1,dp[i]);
}
for(int i=1;i<=n;i++){
if(dp[i]==ans1){
ans2[10]+=b[10][i];
ans2[9]+=b[9][i];
ans2[8]+=b[8][i];
ans2[7]+=b[7][i];
ans2[6]+=b[6][i];
ans2[5]+=b[5][i];
ans2[4]+=b[4][i];
ans2[3]+=b[3][i];
ans2[2]+=b[2][i];
ans2[1]+=b[1][i];
ans2[2]+=ans2[1]/10000000;
ans2[1]%=10000000;
ans2[3]+=ans2[2]/10000000;
ans2[2]%=10000000;
ans2[4]+=ans2[3]/10000000;
ans2[3]%=10000000;
ans2[5]+=ans2[4]/10000000;
ans2[4]%=10000000;
ans2[6]+=ans2[5]/10000000;
ans2[5]%=10000000;
ans2[7]+=ans2[6]/10000000;
ans2[6]%=10000000;
ans2[8]+=ans2[7]/10000000;
ans2[7]%=10000000;
ans2[9]+=ans2[8]/10000000;
ans2[8]%=10000000;
ans2[10]+=ans2[9]/10000000;
ans2[9]%=10000000;
}
}
cout<<ans1<<" ";
for(int i=10;i>=1;i--){
if(ans2[i]){
cout<<ans2[i--];
while(i){
for(int j=10000000;j>=10;j/=10){
ans2[i]%=j;
cout<<ans2[i]/(j/10);
}
i--;
}
}
}
return 0;
}