看到“你必须用低于你上次购买它的价格购买它”，有没有想到什么？没错，又是LIS，倒过来的LIS，所以我们只要把读入的序列倒过来就可以求LIS了，第一问解决。
首先要厘清的是，对于这一题第二问貌似用\(nlog_{2}n\)的算法不是很好，因为我们需要序列中每一个位置可以接成LIS的长度。再看看数据范围，会发现\(n^2\)完全可做。仔细想一想，不难发现第二问其实也是个\(DP\)：若\(f[i]\)表示以\(i\)位置为结尾的LIS的长度，\(c[i]\)表示序列\(1\)~\(i\)位置按照最优选择的方案数，则状态转移方程\(c[i]=\sum\limits_{1\leqslant j<i,a[i]>a[j],f[i]=f[j]+1}c[j]\)，同时还要去重\(c[i]-=\sum\limits_{1\leqslant j<i,a[i]=a[j],f[i]=f[j]}c[j]\)。
代码
``` cpp #includeusing namespace std;
const int N = 5005;
int n, a[N], f[N], c[N], ans1, ans2;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[n+1-i];
for(int i = 1; i <= n; i++) { \常规n^2解法
f[i] = 1;
for(int j = 1; j < i; j++)
if(a[i]>a[j]) f[i] = max(f[i], f[j]+1);
ans1 = max(ans1, f[i]);
}
for(int i = 1; i <= n; i++) {
if(f[i] == 1) c[i] = 1; \初始化
for(int j = 1; j < i; j++) {
if(f[i] == f[j] && a[i] == a[j]) c[i] -= c[j]; \去重
if(f[i] == f[j]+1 && a[i] > a[j]) c[i] += c[j]; \状态转移
}
}
for(int i = 1; i <= n; i++)
if(f[i] == ans1) ans2 += c[i]; \统计答案
cout << ans1 << " " << ans2;
return 0;
}