分析
这是一道求最长下降子序列的题目，且要统计方案，但是会有重复情况，例如以下的的数据，
4
4 2 2 3
我们可以选择 \(1, 2\), \(1, 2\), \(1, 4\) 这几天来购买，但是 \(1, 2\) 和 \(1, 3\) 本质上是一样的，所以只算一种。
根据上面的说明，我们可以得出：
- 当 \(dp_j + 1 = dp_i\) 而且 \(a_j > a_i\)，\(i\) 的方案数加上 \(j\) 的方案数。
- 当 \(dp_j = dp_i\) 而且 \(a_j = a_i\)，\(j\) 的方案数清零。
其中 \(dp_i\) 指以第 \(i\) 个数为结尾的最长公共下降子序列长度，\(a_i\) 指第 \(i\) 天的股票价格。
90 pts Code
/*Code By Manipula*/
#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define INF 0x3f3f3f3f
#define int long long
#define swap(x, y) x ^= y ^= x ^= y
#define sqrt(n) pow(n, 0.5)
#define sort stable_sort
#define mk(x, y) make_pair(x, y)
#define mt(arr, num) memset(arr, num, sizeof(arr))
using namespace std;
const int N = 5005;
int dp[N], a[N], ans[N], n, last, sum;
signed main()
{
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i];
for (int i = 1; i <= n; i++)dp[i] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < i; j++)
if (a[j] > a[i])dp[i] = max(dp[i], dp[j] + 1);
if (dp[i] > dp[last])last = i;
}
for (int i = 1; i <= n; i++)
{
if (dp[i] == 1)ans[i] = 1;
for (int j = 1; j < i; j++)
if (a[j] > a[i] && dp[j] + 1 == dp[i])ans[i] += ans[j];
else if (a[j] == a[i] && dp[j] == dp[i])ans[j] = 0;
}
for (int i = 1; i <= n; i++)
if (dp[i] == dp[last])sum += ans[i];
cout << dp[last] << " " << sum;
return 0;
}
为什么是 90 pts 代码？因为这题要打十分讨厌的高精度！！
下面给出加上了高精度的代码。
Accepted Code
/*Code By Manipula*/
#include <bits/stdc++.h>
// #pragma GCC optimize(2)
#define INF 0x3f3f3f3f
#define int long long
#define swap(x, y) x ^= y ^= x ^= y
#define sqrt(n) pow(n, 0.5)
#define sort stable_sort
#define mk(x, y) make_pair(x, y)
#define mt(arr, num) memset(arr, num, sizeof(arr))
using namespace std;
const int N = 5005;
const int base = 1e18;
int dp[N], a[N], n, last;
struct BIGNUM{
int num[N], len;
void meset(){mt(num, 0); len = 1;}
BIGNUM operator + (BIGNUM a) const {
BIGNUM res = (BIGNUM){{}, max(a.len, len)};
for (int i = 1; i <= res.len; i++)
{
res.num[i] += a.num[i] + num[i];
res.num[i + 1] += res.num[i] / base;
res.num[i] %= base;
}
if (res.num[res.len + 1])res.len++;
return res;
}
void print()
{
for (int i = len; i; i--)
if (i == len)cout << num[i];
else cout << setw(18) << setfill('0') << num[i];
}
}ans[N], sum;
signed main()
{
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i];
for (int i = 1; i <= n; i++)dp[i] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < i; j++)
if (a[j] > a[i])dp[i] = max(dp[i], dp[j] + 1);
if (dp[i] > dp[last])last = i;
}
for (int i = 1; i <= n; i++)
{
if (dp[i] == 1)ans[i] = (BIGNUM){{0, 1}, 1};
for (int j = 1; j < i; j++)
if (a[j] > a[i] && dp[j] + 1 == dp[i])ans[i] = ans[i] + ans[j];
else if (a[j] == a[i] && dp[j] == dp[i])ans[j].meset();
}
for (int i = 1; i <= n; i++)
if (dp[i] == dp[last])sum = sum + ans[i];
cout << dp[last] << " ";
sum.print();
return 0;
}