当前位置：首页 > news >正文

牛客刷题-Day6

news 2025/9/28 10:41:27

牛客刷题-Day5

今日刷题：$1026-1030$

1026 合并回文子串

题目描述

输入两个字符串 $A$ 和 $B$，合并成一个串 $C$，属于 $A$ 和 $B$ 的字符在 $C$ 中顺序保持不变。如 abc 和 xyz 可以被组合成 axbycz 或 abxcyz 等。
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如 aba 和 xyyx）。
需要求出所有可能的 $C$ 中价值最大的字符串，输出这个最大价值即可。

输入描述

第一行一个整数 $T$（$T ≤ 50$）。
接下来 $2T$ 行，每两行两个字符串分别代表 $A$，$B$（$|A|,|B| ≤ 50$），$A$，$B$ 的字符集为全体小写字母。

输出描述

对于每组数据输出一行一个整数表示价值最大的 $C$ 的价值。

示例

输入

2
aa
bb
a
aaaabcaa

输出

4
5

解题思路

之前做关于回文子串的动态规划题目，是以 $f_{i,j}$ 表示区间字符串 $[i,j]$ 是否为回文串或者回文子串，是对单个字符串的状态表示，但该题目涉及两个字符串。关于 $f_{i,j,p,q}$ 表示字符串 $A$ 的 $[i,j]$ 与 $B$ 的 $[p,q]$ 是否构成回文子串的状态表示没有第一时间想出来，能力还是欠缺。

状态表示：$f_{i,j,p,q}$ 表示字符串 $A$ 的 $[i,j]$ 与 $B$ 的 $[p,q]$ 是否构成回文串；
状态计算：题目中提到 $A$ 和 $B$ 合并成的串的字符在 $C$ 中的顺序保持不变，那么 $A$ 的 $[i,j]$ 与 $B$ 的 $[p,q]$ 构成的串的首元素来自 $A_i$ 或者 $B_p$，尾元素来自 $A_j$ 或者 $B_q$，因此共存在 $A_i=A_j$、$A_i=B_q$、$B_p=A_j$、$B_p=B_q$ 四种情况，故

if (A[i] == A[j]) f[i][j][p][q] |= f[i + 1][j - 1][p][q];
if (A[i] == B[q]) f[i][j][p][q] |= f[i + 1][j][p][q - 1];
if (B[p] == A[j]) f[i][j][p][q] |= f[i][j - 1][p + 1][q];
if (B[p] == B[q]) f[i][j][p][q] |= f[i][j][p + 1][q - 1];

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 55;int T;
string A, B;
bool f[N][N][N][N];int main() {cin >> T;while (T--) {memset(f, 0, sizeof f);cin >> A >> B;A = "#" + A, B = "#" + B;int n = A.size(), m = B.size(), ans = 1;for (int len1 = 0; len1 <= n; len1++)for (int len2 = 0; len2 <= m; len2++)for (int i = 1; i + len1 - 1 < n; i++)for (int p = 1; p + len2 - 1 < m; p++) {int j = i + len1 - 1, q = p + len2 - 1;if (len1 + len2 <= 1)f[i][j][p][q] = 1;else {if (A[i] == A[j]) f[i][j][p][q] |= f[i + 1][j - 1][p][q];if (A[i] == B[q]) f[i][j][p][q] |= f[i + 1][j][p][q - 1];if (B[p] == A[j]) f[i][j][p][q] |= f[i][j - 1][p + 1][q];if (B[p] == B[q]) f[i][j][p][q] |= f[i][j][p + 1][q - 1];}if (f[i][j][p][q])ans = max(ans, len1 + len2);}cout << ans << endl;}return 0;
}

1027 取数游戏2

题目描述

给定两个长度为 $n$ 的整数列 $A$ 和 $B$，每次你可以从 $A$ 数列的左端或右端取走一个数。假设第 $i$ 次取走的数为 $a_x$，则第 $i$ 次取走的数的价值 $v_i=b_i⋅a_x$，现在希望你求出 $∑v_i$ 的最大值。

输入描述

第一行一个数 $T$，表示有 $T$ 组数据。
对于每组数据，第一行一个整数 $n$，
接下来两行分别给出 $A$ 数列与 $B$ 数列。

输出描述

每一组数据输出一行，最大的 $∑v_i$。

示例

输入

输出

2001
52

说明
对于第二个样例，
第一次从左边取走 $a_1$，$v_1=a_1⋅b_1=1$，
第二次从左边取走 $a_2$，$v_2=a_2⋅b_2=6$，
第三次从右边取走 $a_5$，$v_3=a_5⋅b_3=12$，
第四次从右边取走 $a_4$，$v_4=a_4⋅b_4=8$，
第五次取走剩下的 $a_3$，$v_5=a_3⋅b_5=25$，
总价值 $∑v_i=1+6+12+8+25=52$。

备注

$T≤10;1≤n≤10^3;1≤a_i,b_i≤10^3$

解题思路

这道题比较简单，可以逆向解决：根据题意，从最后取走的元素往两边扩展。

状态表示：$f_{i,j}$ 表示区间 $[i,j]$ 的元素已被取走的价值和，则取的要么是 $a_i$，要么是 $a_j$，故状态转移方程 $f_{i,j}=max\{f_{i+1,j}+a_i*b_k,f_{i,j-1}+a_j*b_k\},k=j-i+1$，这里将 $b$ 数组进行了翻转。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;int T, n;
int a[N], b[N];
int f[N][N]; // [i, j] 已取走的价值和int main() {scanf("%d", &T);while (T--) {memset(f, 0, sizeof f);scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);for (int i = 1; i <= n; i++)scanf("%d", &b[i]);reverse(b + 1, b + n + 1);for (int i = 1; i <= n; i++)f[i][i] = a[i] * b[1];for (int i = n; i >= 1; i--)for (int j = i + 1; j <= n; j++) {int k = j - i + 1;f[i][j] = max(f[i + 1][j] + a[i] * b[k], f[i][j - 1] + a[j] * b[k]);}printf("%d\n", f[1][n]);}return 0;
}

1028 wyh的问题

题目描述

我国现在能源消耗非常严重，现在政府有这样一个工作，每天早上都需要把一些路灯关掉，但是他们想让在关闭的过程中所消耗的能源是最少的，负责路灯关闭的工作人员以 $1m/s$ 的速度进行行走，假设关闭路灯的时候不需要花费任何的时间，请你编写一个程序，计算在给定路灯位置和每个路灯的消耗能源的多少，求出当所有路灯关闭的时候所需要的最少能量。

输入描述

多组测试数据循环输入。
每组测试数据第一行：$N$ 表示路灯的数量。（$2<=N <=1000$）
第二行：$V$ 表示开始关灯的路灯号码。（$1<=V<=N$）
接下来的 $N$ 行中，每行包含两个用空格隔开的整数 $D$ 和 $W$，用来描述每盏灯的参数。
$D$ 表示该路灯到原点的距离 (用米为单位来表示)，
$W$ 表示灯泡的功率，即每秒该灯泡所消耗的能量数。（$0<=D<=1000$，$0<=W<=1000$）
路灯按照顺序给出，起始位置的那盏灯不算消耗的电能里面。

输出描述

输出一个整数，即消耗能量之和的最小值。

示例

输入

输出

说明
对于样例，一开始在第三个路灯的位置，即在 $6$ 位置；
第 $1s$ 的时候去 $5$ 把第二盏灯关闭，消耗电能 $8$；
然后去第四盏灯，第四盏灯亮的时间是 $4s$，所以消耗电能 $28$；
最后去关第一盏灯第一盏灯亮的时间是 $10s$，所以消耗电能 $20$；
最后总和为 $8+28+20=56$。

解题思路

洛谷之前做过类似的题目：P1220 关路灯。
关灯，从起点往两边依次进行，要么往左要么往右，然后来回折返。

状态表示：$f_{i,j,0}$ 表示 $[i,j]$ 的灯已关闭，且最后在 $i$ 处的电能消耗；$f_{i,j,1}$ 表示 $[i,j]$ 的灯已关闭，且最后在 $j$ 处的电能消耗。这里 $i$ 和 $j$ 为路灯的索引，不是路灯具体的位置，因为数据是按照顺序给出的。
状态计算：因为速度的原因，这里距离的数值和时间是相同的。

\[f_{i,j,0}=min\{f_{i+1,j,0}+(d_{i+1}-d_{i})*(s_i+s_n-s_{j}),f_{i+1,j,1}+(d_{j}-d_{i})*(s_i+s_n-s_{j})\} \]

\[f_{i,j,1}=min\{f_{i,j-1,0}+(d_{j}-d_{i})*(s_{i-1}+s_n-s_{j-1}),f_{i,j-1,1}+(d_{j}-d_{j-1})*(s_{i-1}+s_n-s_{j-1})\} \]

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef long long LL;int n, v;
struct Light {int d, w;
} a[N];
LL s[N], f[N][N][2]; // i 到 j 索引的灯已关闭int main() {while (scanf("%d", &n) != EOF) {scanf("%d", &v);for (int i = 1; i <= n; i++)scanf("%d%d", &a[i].d, &a[i].w);memset(f, 0x3f, sizeof f);for (int i = 1; i <= n; i++)s[i] = s[i - 1] + a[i].w;f[v][v][0] = f[v][v][1] = 0;for (int len = 2; len <= n; len++)for (int i = 1; i + len - 1 <= n; i++) {int l = i, r = i + len - 1;f[l][r][0] = min(f[l + 1][r][0] + (a[l + 1].d - a[l].d) * (s[l] + s[n] - s[r]), f[l + 1][r][1] + (a[r].d - a[l].d) * (s[l] + s[n] - s[r]));f[l][r][1] = min(f[l][r - 1][0] + (a[r].d - a[l].d) * (s[l - 1] + s[n] - s[r - 1]), f[l][r - 1][1] + (a[r].d - a[r - 1].d) * (s[l - 1] + s[n] - s[r - 1]));}printf("%lld\n", min(f[1][n][0], f[1][n][1]));}return 0;
}

1029 [NOIP2007]矩阵取数游戏

题目描述

帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 $n*m$ 的矩阵，矩阵中的每个元素 $a_{ij}$ 均为非负整数。游戏规则如下：

每次取数时须从每行各取走一个元素，共 $n$ 个。$m$ 次后取完矩阵所有元素；
每次取走的各个元素只能是该元素所在行的行首或行尾；
每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值$ * 2^i$，其中 $i$ 表示第 $i$ 次取数（从 $1$ 开始编号）；
游戏结束总得分为 $m$ 次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

输入描述

第 $1$ 行为两个用空格隔开的整数 $n$ 和 $m$。
第 $2~n+1$ 行为 $n*m$ 矩阵，其中每行有 $m$ 个用单个空格隔开的非负整数。

输出描述

输出一个整数，即输入矩阵取数后的最大得分。

示例1

输入

2 3
1 2 3
3 4 2

输出

说明
第 $1$ 次：第1行取行首元素，第2行取行尾元素，本次得分为 $1 * 2^1 + 2 * 2^1 = 6$；
第 $2$ 次：两行均取行首元素，本次得分为 $2 * 2^2 + 3 * 2^2 = 20$；
第 $3$ 次：得分为 $3 * 2^3 + 4 * 2^3 = 56$；
总得分为 $6 + 20 + 56 = 82$。

示例2

输入

1 4
4 5 0 5

输出

示例3

输入

2 10
96 56 54 46 86 12 23 88 80 43
16 95 18 29 30 53 88 83 64 67

输出

备注

$60\%$ 的数据满足：$1 ≤ n, m ≤ 30$，答案不超过 $10^{16}$
$100\%$ 的数据满足：$1 ≤ n, m ≤ 80$，$0 ≤ a_{i,j} ≤ 1000$

解题思路

根据题意，每行的取数都是独立的，因此我们对每行进行操作，最后所有加起来即可，思路类似 $1027$。
要注意数据范围，即使用 long long 也只能过 $60\%$ 的数据。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100;__int128 qmi(__int128 a, int b) {__int128 res = 1;while (b) {if(b & 1) res = res * a;a = a * a;b >>= 1;}return res;
}template <typename T> void Out(T x) {if(x < 0) putchar('-') , x = -x;if(x > 9) Out(x / 10);putchar(x % 10 + '0');
}int n, m;
int a[N][N];
__int128 f[N][N]; // 区间 i 到 j 已取完// __int128只能做加减乘除，判断，移位运算等操作
// 需要自己写输入和输出，一般我们只要会自写输出即可
int main() {cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> a[i][j];__int128 ans = 0;for (int i = 1; i <= n; i++) {memset(f, 0, sizeof f);for (int j = 1; j <= m; j++)f[j][j] = a[i][j] * qmi(2, m);for (int l = m; l >= 1; l--)for (int r = l + 1; r <= m; r++) {int k = m - (r - l);f[l][r] = max(f[l + 1][r] + qmi(2, k) * a[i][l],f[l][r - 1] + qmi(2, k) * a[i][r]);}ans += f[1][m];}Out(ans);return 0;
}

查看全文

http://www.hskmm.com/?act=detail&tid=19769