爱奇艺笔试题
1.对称字符串问题
Time Limit: 1000/1000 MS (Others/C,C++) Memory Limit: 65536/65536
K (Others/C,C++)
Problem Description:
计算给定字符串中的最长对称子串长度，例如“iqiyi”中的最长对称子串为“i”，“iqiyiyiq”的最长对
称子串为“qiyi”和“iyiq”，长度为4。给定字符串为纯小写字母的组合。
输入
输入数据为单行字符串，只含有小写字母，中间无空格。
输出
最长对称子串的长度。
样例输入
iqiyiyiq
abccba
样例输出
4
3
这题直接暴力，或者manacher算法，左老师讲过，自己没有实现过。。。就用了暴力
#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <string>
using namespace std;
void LongestSubStr(const string &str) {
string res(str.size() * 2,'0');
int i, j;
j = 0;
for (i = 0; i < str.size(); i++) {
res[j++] = str[i];
res[j++] = '#';
}
int len = 0;
for (int j = 1; j < res.size(); j++) {
int left = j - 1;
int right = j + 1;
int max = 0;
while (left >= 0 && right < res.size() && res[left] == res[right]) {
left--; right++;
++max;
}
if (max > len)
len = max;
}
if (len == 0) {
printf("%d\n", len + 1);
return;
}
printf("%d\n", (len + 1) / 2);
}
int main()
{
string str;
while(cin >> str)
LongestSubStr(str);
system("pause");
return 0;
}
2.小Q的包裹
Time Limit: 1000/1000 MS (Others/C,C++) Memory Limit: 65536/65536
K (Others/C,C++)
Problem Description:
小Q在国外上学，业余时间兼职代购补贴学费。假定她每周向国内寄回一个包裹，包裹的重量上限是m，小Q的利润是包裹价值的10%。
现在小Q有n件物品准备寄出，每件物品的重量和价值不等，小Q想知道这个包裹最多能获得多少利润？
输入
第一行数据是两个正整数，分别表示包裹的重量上限m和物品的总数n
第二行数据是n个正整数，表示第一件，第二件...第n件物品的重量
第三行数据是n个正整数，表示第一件，第二件...第n件物品的价值
输出
为1个实数，保留小数点后一位，表示小Q在这个包裹上能赚到的利润。
样例输入
10 5
2 2 6 5 4
6 3 5 4 6
样例输出
1.5
这个题是0-1背包问题，直接上代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
//0-1背包问题
void DP(int n, int m) {
float res;
int *weight = new int[m];
int *value = new int[m];
int **dp = new int*[m]; //dp[i][j]表示第i个物品，背包容量为j时的最大价值
for (int i = 0; i < m; i++)
dp[i] = new int[n + 1];
for (int i = 0; i < m; i++)
cin >> weight[i];
for (int i = 0; i < m; i++)
cin >> value[i];
for (int i = 0; i < m; i++)
dp[i][0] = 0;
for (int i = 0; i <= n; i++) { //这里是<=
if (i >= weight[0]) //这里是>=
dp[0][i] = value[0];
else
dp[0][i] = 0;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j <= n; j++) {
if (j < weight[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j] > dp[i - 1][j - weight[i]] + value[i] ? dp[i - 1][j] : dp[i - 1][j - weight[i]] + value[i];
}
}
res = dp[m - 1][n] * 0.1;
printf("%2.1f\n", res);
}
int main()
{
int m, n;
while(cin >> n >> m) //m表示物品种数
DP(n, m);
system("pause");
return 0;
}
