题目
p1108 低价购买
解析
这题做的我身心俱惫,差点自闭。
当我wa了n发后,终于明白了这句话的意思
当二种方案“看起来一样”时(就是说它们构成的价格队列一样的时候),这2种方案被认为是相同的。
这题有两问,第一问显然最长严格下降子序列,一看数据范围:5000,跟最长严格上升子序列一样,(n^2)直接写就行。
第二问求方案数,方案数也是用dp做
转移方程
//j<i if (f[i] == f[j] + 1 && a[j] > a[i]) cnt[i] += cnt[j];
这里还要注意一下相同这种情况,
如果对于两个位置(i,j(j<i))来说,
若(f[i]==f[j]&&a[i]==a[j]),那就说明到(i)与到(j)的这两个最长下降子序列是相同的,算一种情况(显然吧应该)。
又因为我们之前把部分算过一次贡献,不再算一遍,那我们就直接不要它了,所以
if (f[i] == f[j] && a[i] == a[j]) cnt[i] = 0;
代码
#include <bits/stdc++.h> using namespace std; const int n = 1e5 + 10; int n, ans, sum; int a[n], b[n], f[n], cnt[n]; template<class t>inline void read(t &x) { x = 0; int f = 0; char ch = getchar(); while (!isdigit(ch)) f |= (ch == '-'), ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); x = f ? -x : x; return; } int main() { read(n); for (int i = 1; i <= n; ++i) read(a[i]), b[i] = a[i]; sort(b + 1, b + 1 + n); int len = unique(b + 1, b + 1 + n) - b - 1; for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b; for (int i = 1; i <= n; ++i) { f[i] = 1; for (int j = 1; j <= i; ++j) if (a[j] > a[i]) f[i] = max(f[i], f[j] + 1); } for (int i = 1; i <= n; ++i) ans = max(f[i], ans); for (int i = 1; i <= n; ++i) { if (f[i] == 1) cnt[i] = 1; for (int j = 1; j < i; ++j) { if (f[i] == f[j] + 1 && a[j] > a[i]) cnt[i] += cnt[j]; if (f[i] == f[j] && a[i] == a[j]) cnt[i] = 0; } if (f[i] == ans) sum += cnt[i]; } printf("%d %d", ans, sum); return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/603320.html