牛客刷题-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\)。
示例
输入
2
2
1 1000
2 1
5
1 3 5 2 4
1 2 3 4 5
输出
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\))
路灯按照顺序给出,起始位置的那盏灯不算消耗的电能里面。
输出描述
输出一个整数,即消耗能量之和的最小值。
示例
输入
4
3
2 2
5 8
6 1
8 7
输出
56
说明
对于样例,一开始在第三个路灯的位置,即在 \(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\) 为路灯的索引,不是路灯具体的位置,因为数据是按照顺序给出的。
- 状态计算:因为速度的原因,这里距离的数值和时间是相同的。
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
输出
82
说明
第 \(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
输出
122
示例3
输入
2 10
96 56 54 46 86 12 23 88 80 43
16 95 18 29 30 53 88 83 64 67
输出
316994
备注
\(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;
}