目录

• • B. Vittorio Plays with LEGO Bricks（动态规划）
  • • 题意：
    • • 输入1：
      • 输出1：
      • 输入2：
      • 输出2：
    • 解题：
    • 代码：
  • G. Another Wine Tasting Event
  • • 题意：
    • • 样例输入1
      • 输出1
      • 样例输入2
      • 输出2
    • 题解：
    • 代码：

B. Vittorio Plays with LEGO Bricks（动态规划）

题意：

给你 nnn 个数，代表坐标，还给你一个 hhh，问需要多少个 2 * 2 的小方格来做底座，才能让这 nnn 个坐标都可以达到 hhh 高度。

输入1：

4 0
2 7 11 13

输出1：

0

输入2：

4 100
2 7 11 13

输出2：

107

解题：

根据题目给你的nnn的范围和描述不难想出是一个 n3n^{3}n3 的动态规划问题， 然后 n3n^{3}n3 的动态规划首先想到的就是区间动态规划。
定义dp[i][j]dp[i][j]dp[i][j]为，从下标 iii 到下标 jjj 的最小需要的方格数，设 kkk 为分割点，leslesles 为两区间公共部分

代码：

#include using namespace std;typedef long long LL;
const int N = 5e5 + 10;LL a[N];void solve()
{LL n, h;cin >> n >> h;for (int i = 1; i <= n; i ++ ) cin >> a[i];vector> dp(n + 1, vector(n + 1, 1ll << 60));for (int i = 1; i <= n; i ++ ) dp[i][i] = h;for (int k = 2; k <= n; k ++ ){for (int i = 1; i + k - 1 <= n; i ++ ){int j = i + k - 1;int g = max(0ll, h - (a[j] - a[i] - 1) / 2);for (int x = i; x < j; x ++ ) dp[i][j] = min(dp[i][j], dp[i][x] + dp[x + 1][j] - g);}}cout << dp[1][n] << '\n';
}int main()
{int T = 1;while (T -- ){solve();}return 0;
}

G. Another Wine Tasting Event

题意：

nnn 个评委，还有一个由W和R组成的字符串，字符串的长度为2∗n−12 * n - 12∗n−1，问nnn个不同的连续的子字符串的最大W含有量是多少。

样例输入1

5
RWWRRRWWW

输出1

2

样例输入2

1
R

输出2

0

题解：

长度为 2∗n−12 * n - 12∗n−1 的字符串，还要nnn个不同的连续的子字符串，那肯定用长度为 nnn 就可以做到了，所以只要注意一下末尾边界处理就可以了，具体看代码理解吧。

代码：

#include using namespace std;#define IOS                      \ios::sync_with_stdio(false); \cin.tie(0);                  \cout.tie(0);typedef long long LL;
typedef pair PII;const int N = 2e6 + 10;void solve()
{int n;string s;cin >> n >> s;s = ' ' + s;int now = 0, ans = 0;for (int i = 1; i <= 2 * n - 1; i ++ ){if (s[i] == 'W') now ++;// cout << now << '\n';ans = max(ans, now);if (i >= n) now -= (s[i - n + 1] == 'W');}cout << ans << '\n';
}int main()
{IOS // ios 优化一下，不然1e6的数据要被卡int T = 1;// cin >> T;while (T -- ){solve();}return 0;
}