背包与魔法本质上升序列

mi0e

March 22, 2023

1004 views

No comments

708 words

C/C++

# 背包与魔法

## 状态机 + 01背包

### 问题描述

小蓝面前有 **N** 件物品, 其中第 **i** 件重量是 **Wi**, 价值是 **Vi** 。她还有一个背包, 最大承重是 **M** 。

小蓝想知道在背包称重范围内, 她最多能装总价值多少的物品?

特别值得一提的是, 小蓝可以使用一个魔法 (总共使用一次), 将一件物品 的重量增加 **K**, 同时价值秝倍。(当然小蓝也可以不使用魔法)

### 输入格式

第一行包含 3 个整数 **N**、**M** 和 **K** 。

以下 **N** 行, 每行两个整数 **Wi** 和 **Vi** 。

### AC

`0 状态` ：还未从施加魔法

`1 状态` ：已经施加过魔法

`1`只能从 `0`转移

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, M = 10010;

int n, m, k;
int dp[N * M][2], w[N], v[N];

int main() {
    cin >> n >> m >> k;

for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

for (int i = 1; i <= n; i++) {
        for (int j = m; j >= w[i]; j--) {
            dp[j][0] = max(dp[j][0], dp[j - w[i]][0] + v[i]);
            if (w[i] + k <= j)
                dp[j][1] = max(max(dp[j][1], dp[j - w[i]][1] + v[i]), dp[j - (w[i] + k)][0] + 2 * v[i]);
        }
    }
    cout << max(dp[m][0], dp[m][1]);

return 0;
}
```

# 本质上升序列

##小蓝特别喜欢单调递增的事物。

在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。

例如，在字符串 `lanqiao` 中，如果取出字符 `n` 和 `q`，则 `nq` 组成一个单调递增子序列。类似的单调递增子序列还有 `lnq、i、ano` 等等。 小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符可以取到 `ao`，取最后两个字符也可以取到 `ao`。小蓝认为他们并没有本质不同。

对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个？ 例如，对于字符串 lanqiao，本质不同的递增子序列有 21 个。它们分别是 `l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、anq、lno、ano、aio`。

请问对于以下字符串（共 200**2**0**0** 个小写英文字母，分四行显示）：

```txt
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
```

本质不同的递增子序列有多少个？

### AC

上升子序列个数 `if (str[i] > str[j]) dp[i] += dp[j]`

去重 `if (str[i] == str[j]) dp[i] -= dp[j]`

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 205;

string str = "atocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf\
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij\
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad\
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
int dp[N], res, cnt = 1;

int main() {
    int n = str.length();
    for (int i = 1; i < n; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++) {
            if (str[j] < str[i]) dp[i] += dp[j];
            if (str[i] == str[j]) dp[i] -= dp[j];
        }
        res += dp[i];
    }

cout << res;

return 0;
}
```

Last modification：March 22, 2023