P1108 低价购买 (DP)
2024-10-21 07:51:54
题目
解析
这题做的我身心俱惫,差点自闭。
当我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;
}
最新文章
- 高效而稳定的企业级.NET Office 组件Spire(.NET组件介绍之二)
- 国内优秀的Android资源
- linux下MySQL安装及设置
- STM32F4读写内部FLASH【使用库函数】
- How to select Multiple images from UIImagePickerController [duplicate]
- 初识echarts
- 【uTenux实验】互斥体
- php 倒计时程序
- gulp基础使用总结
- NFC(12)使用Android Beam技术传输文本数据及它是什么
- Android - Ashmem驱动
- 【转】Win7+Ubuntu12.04.1硬盘安装错误及解决方案----不错
- centos 安装amp 运行环境+配置虚拟地址
- IDEA+PHP+XDebug调试配置
- idea和androidstudio的首次git配置一些问题
- springboot~ EventListener事件监听的使用
- 你不需要 jQuery,但你需要一个 DOM 库
- HBase读写的几种方式(一)java篇
- String Method的字符串变换的一个例子
- Tajima&#39;s D