Scratch编程一级 题库
图像处理
给定n行m列的图像各像素点的灰度值,要求用如下方法对其进行模糊化处理:
1. 四周最外侧的像素点灰度值不变;
2. 中间各像素点新灰度值为该像素点及其上下左右相邻四个像素点原灰度值的平均(舍入到最接近的整数)。
时间限制:1000
内存限制:65536
输入
第一行包含两个整数n和m,表示图像包含像素点的行数和列数。1 <= n <= 100,1 <= m <= 100。 接下来n行,每行m个整数,表示图像的每个像素点灰度。相邻两个整数之间用单个空格隔开,每个元素均在0~255之间。
输出
n行,每行m个整数,为模糊处理后的图像。相邻两个整数之间用单个空格隔开。
样例输入
4 5 100 0 100 0 50 50 100 200 0 0 50 50 100 100 200 100 100 50 50 100
样例输出
100 0 100 0 50 50 80 100 60 0 50 80 100 90 200 100 100 50 50 100
#include <cmath>
#include <iostream>
using namespace std;
const int N = 100 + 10;
int a[N][N], b[N][N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
b[i][j] = a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == n || i == 1 || j == m || j == 1)
continue;
else {
double sum =
a[i][j] + a[i - 1][j] + a[i + 1][j] + a[i][j - 1] + a[i][j + 1];
sum /= 5;
b[i][j] = int(round(sum));
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j == 1)
cout << b[i][j];
else
cout << ' ' << b[i][j];
}
cout << endl;
}
}偶数降序输出
给定一个长度为N (不大于500) 的正整数序列,请将其中的所有偶数取出,并按降序输出。
输入描述:
共两行;第一行为N;第二行为N个正数,其间用空格间隔
输出描述:
降序输出的偶数序列,数与数之间用空格间隔
数据保证至少有一个偶数
样例输入:
10
1 3 2 6 5 4 9 8 7 10
样例输出:
10 8 6 4 2
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int a[N];
bool cmp(int num1, int num2) { return num1 >= num2; }
main() {
int n, t;
int j = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
if (a[i] % 2 == 0) {
t = a[i];
a[j++] = t;
}
}
sort(a, a + j, cmp);
for (int i = 0; i < j; i++) {
cout << a[i] << " ";
}
cout << endl;
}满足条件的数的累加2
现有n个整数,将其中个位数为k的数进行累加求和
输入
第一行一个整数n。第二行n个非负整数,以空格分割,每个数不大于100000。第三行一个整数k。
输出
输出满足题目要求的累加和
样例输入
10 2 5 7 17 11 18 4 27 1 7 7
样例输出
58
#include <iostream>
using namespace std;
int main() {
int n, sum = 0;
cin >> n;
int a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int k;
cin >> k;
for (int i = 0; i < n; i++) {
if (a[i] % 10 == k) { // 个位数
sum += a[i];
}
}
cout << sum;
return 0;
}//解法2
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k,ans=0;
cin>>n>>k;
for(int i=1,x;i<=n;i++){
cin>>x;
if(x%10==k) ans+=x;
}
cout<<ans;
return 0;
}数字判断
输入一个字符,如果输入的字符是数字,输出yes,否则输出no
输入
一个字符
输出
如果输入的字符是数字,输出yes,否则输出no
样例1输入
5
样例1输出
yes
样例2输入
A
样例2输出
no
#include <iostream>
using namespace std;
int main() {
char ch;
cin >> ch;
if (ch >= '0' && ch <= '9') {
cout << "yes";
} else {
cout << "no";
}
return 0;
}满足条件的数的累加
现有n个整数,将其中个位数为k的数进行累加求和。
输入
第一行2个整数n、k,以空格隔开。(0<n<1000,0<=k<=9) 第二行n个非负整数,以空格隔开,每个数不大于100000。
输出
输出满足题目要求的累加和。
样例输入
10 7 2 5 7 17 11 18 4 27 1 7
样例输出
58
//解法1
#include <iostream>
using namespace std;
int main() {
int n, k, a, sum = 0;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a;
if (a % 10 == 7)
sum += a;
}
cout << sum;
return 0;
}//解法2
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k,ans=0;
cin>>n>>k;
for(int i=1,x;i<=n;i++){
cin>>x;
if(x%10==k) ans+=x;
}
cout<<ans;
return 0;
}交换输出
输入两个整数a,b,将它们交换输出
输入
一行两个整数a、b,以空格分割。0<a<108 0<b<1016
输出
一行两个整数b、a,以空格分割。
样例输入
123 12345654321
样例输出
12345654321 123
#include <iostream>
using namespace std;
int main() {
long long a, b;
cin >> a >> b;
cout << b << " " << a;
}比n小的最大质数
对于给定的n,求比n小的质数中最大的一个
质数是指大于1的自然数,除了1和它自身外,不能被其他自然数整除的数。
输入
一个整数n(2<n<1000)
输出
一个整数,即题目要求的解。
样例输入
100
样例输出
97
#include <iostream>
using namespace std;
bool isPrime(int x) {
for (int i = 2; i < x; i++) {
if (x % i == 0)
return false;
}
return true;
}
int main() {
int n;
cin >> n;
while (n > 0) {
if (isPrime(n)) {
cout << n;
break;
}
n--;
}
return 0;
}逆波兰表达式
逆波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值,其中运算符包括+ - * /四个。
时间限制:1000
内存限制:65536
输入
输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。
输出
输出为一行,表达式的值。 可直接用printf("%f\n", v)输出表达式的值v。
样例输入
* + 11.0 12.0 + 24.0 35.0
样例输出
1357.000000
#include <cmath>
#include <cstdlib>
#include <iostream>
using namespace std;
const int N = 40;
char a[N];
double expr(void) {
scanf("%s", a);
if (a[0] == '+')
return expr() + expr();
else if (a[0] == '-')
return expr() - expr();
else if (a[0] == '*')
return expr() * expr();
else if (a[0] == '/')
return expr() / expr();
else
return atof(a);
}
int main() {
printf("%lf\n", expr());
return 0;
}有多少种二叉树
输入n(1<n<13),求n个结点的二叉树有多少种形态
时间限制:1000
内存限制:65536
输入
整数n
输出
答案
样例输入
3
样例输出
5
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n, h1 = 1, y = 0;
cin >> n;
for (long long i = 1; i < n + 1; i++) {
y = (4 * i - 2) * h1 / (i + 1);
h1 = y;
}
cout << y;
return 0;
}快速堆猪
小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。
时间限制:1000
内存限制:65536
输入
有三种输入 1)push n n是整数(0<=0 <=20000),表示叠上一头重量是n斤的新猪 2)pop 表示将猪堆顶的猪赶走。如果猪堆没猪,就啥也不干 3)min 表示问现在猪堆里最轻的猪多重。如果猪堆没猪,就啥也不干 输入总数不超过100000条
输出
对每个min输入,输出答案。如果猪堆没猪,就啥也不干
样例输入
pop min push 5 push 2 push 3 min push 4 min
样例输出
2 2
#include <iostream>
using namespace std;
typedef long long LL;
int h[2005];
int size_;
void up(int u) {
while (u / 2 && h[u / 2] > h[u]) {
swap(h[u / 2], h[u]);
u /= 2;
}
}
void down(int u) {
int t = u;
if (u * 2 <= size_ && h[u * 2] < h[u])
t = u * 2;
if (u * 2 + 1 <= size_ && h[u * 2 + 1] < h[u])
t = u * 2 + 1;
if (u != t) {
swap(h[u], h[t]);
down(t);
}
}
int main() {
char t[10];
string s;
int n;
while (scanf("%s", t) != EOF) {
s = string(t);
if (s == "pop") {
if (size_ == 0)
continue;
h[1] = h[size_];
size_--;
down(1);
} else if (s == "min") {
if (size_ == 0)
continue;
cout << h[1] << endl;
} else if (s == "push") {
cin >> n;
size_++;
h[size_] = n;
up(size_);
}
}
return 0;
}小白鼠再排队2
N只小白鼠(1 < N < 100),每只鼠头上戴着一顶有颜色的帽子。现在称出每只白鼠的重量,要求按照白鼠重量从小到大的顺序输出它们头上帽子的颜色。帽子的颜色用 “red”,“blue”等字符串来表示。不同的小白鼠可以戴相同颜色的帽子。白鼠的重量用整数表示。
时间限制:1000
内存限制:65536
输入
输入第一行为一个整数N,表示小白鼠的数目。 下面有N行,每行是一只白鼠的信息。第一个为正整数,表示白鼠的重量,不超过整型范围;第二个为字符串,表示白鼠的帽子颜色,字符串长度不超过10个字符。 注意:白鼠的重量各不相同。
输出
按照白鼠的重量从小到大的顺序输出白鼠的帽子颜色。
样例输入
3 30 red 50 blue 40 green
样例输出
red green blue
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
struct sb {
int z;
char s[15];
} a[105];
bool cmp(sb a, sb b) { return a.z < b.z; }
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].z >> a[i].s;
}
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < strlen(a[i].s); j++) {
cout << a[i].s[j];
}
cout << endl;
}
return 0;
}夺宝探险
你无意中发现了装满了宝藏的迷宫,你想要获得尽可能多的宝藏,但是迷宫里的机关阻碍了你的计划。迷宫的地面是M行N列的矩形网格,每格是一块带有机关且放置了1个宝藏的地砖,宝藏一共有K种,用1-K表示其种类,迷宫的入口只有一个,为迷宫的第一行第一列。地砖的机关如下:
1. 每次你只能踏到你与你所在地砖相邻的地砖上(即前后左右4块);
2. 当你踏上某块地砖后,其上的宝藏(假设种类为k)自动归属你,同时所有放置了种类为k的宝藏的地砖碎裂,你无法踏上,你当前所在的地砖在你离开后也会立刻碎裂;
3. 当你无路可走的时候,你会被传送回迷宫出口,无法再进入迷宫。
你想知道你最多能获得多少宝藏。
时间限制:1000
内存限制:65536
输入
输入的第一行是三个用空格隔开的整数,分别是M、N和K(1 <= M,N <= 20, 1 <= K <= 100) 之后是M行,每行包含N个范围为1-K的整数,用空格隔开,表示放置的宝藏种类
输出
只有一行,为一个整数,表示最多能获得的宝藏个数。
样例输入
3 4 5 1 2 3 3 2 1 4 3 1 5 1 2
样例输出
4
#include <iostream>
using namespace std;
int m, n, k;
int a[22][22];
bool jewel[101];
int have = 0; // 获得的宝石数
int ans = 0;
int dirx[4] = {0, 0, 1, -1};
int diry[4] = {1, -1, 0, 0};
void dfs(int x, int y) {
for (int i = 0; i < 4; i++) {
int nx = x + dirx[i];
int ny = y + diry[i];
if (!jewel[a[nx][ny]]) {
jewel[a[nx][ny]] = true;
have++;
dfs(nx, ny);
have--;
jewel[a[nx][ny]] = false;
}
}
ans = max(ans, have);
}
int main() {
cin >> m >> n >> k;
int i, j;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
cin >> a[i][j];
jewel[a[1][1]] = true;
jewel[0] = true;
have = 1;
dfs(1, 1);
cout << ans;
return 0;
}晶矿的个数
在某个区域发现了一些晶矿,已经探明这些晶矿总共有分为两类,为红晶矿和黑晶矿。现在要统计该区域内红晶矿和黑晶矿的个数。假设可以用二维地图m[][]来描述该区域,若m[i][j]为#表示该地点是非晶矿地点,若m[i][j]为r表示该地点是红晶矿地点,若m[i][j]为b表示该地点是黑晶矿地点。一个晶矿是由相同类型的并且上下左右相通的晶矿点组成。现在给你该区域的地图,求红晶矿和黑晶矿的个数。
时间限制:1000
内存限制:65536
输入
第一行为k,表示有k组测试输入。 每组第一行为n,表示该区域由n*n个地点组成,3 <= n<= 30 接下来n行,每行n个字符,表示该地点的类型。
输出
对每组测试数据输出一行,每行两个数字分别是红晶矿和黑晶矿的个数,一个空格隔开。
样例输入
2 6 r##bb# ###b## #r##b# #r##b# #r#### ###### 4 #### #rrb #rr# ##bb
样例输出
2 2 1 2
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
char b[N][N + 1];
int n;
void dfs(int r, int c, char type) {
if (r < 0 || r >= n || c < 0 || c >= n)
return;
if (b[r][c] != type)
return;
b[r][c] = '#';
dfs(r - 1, c, type);
dfs(r + 1, c, type);
dfs(r, c - 1, type);
dfs(r, c + 1, type);
}
int main() {
int k;
scanf("%d", &k);
while (k--) {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%s", b[i]);
int rcnt = 0, bcnt = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (b[i][j] == 'r') {
rcnt++;
dfs(i, j, 'r');
} else if (b[i][j] == 'b') {
bcnt++;
dfs(i, j, 'b');
}
printf("%d %d\n", rcnt, bcnt);
}
return 0;
}小白鼠再排队
N只小白鼠(1 < N < 100),每只鼠头上戴着一顶有颜色的帽子。现在称出每只白鼠的重量,要求按照白鼠重量从小到大的顺序输出它们头上帽子的颜色。帽子的颜色用 “red”,“blue”等字符串来表示。不同的小白鼠可以戴相同颜色的帽子。白鼠的重量用整数表示。
时间限制:1000
内存限制:65536
输入
输入第一行为一个整数N,表示小白鼠的数目。 下面有N行,每行是一只白鼠的信息。第一个为正整数,表示白鼠的重量,不超过整型范围;第二个为字符串,表示白鼠的帽子颜色,字符串长度不超过10个字符。 注意:白鼠的重量各不相同。
输出
按照白鼠的重量从小到大的顺序输出白鼠的帽子颜色。
样例输入
3 30 red 50 blue 40 green
样例输出
red green blue
#include <iostream>
using namespace std;
int main() {
int a[100]; // 体重
string b[100]; // 帽子颜色
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i] >> b[i];
for (int i = n - 1; i > 0; i--) // 冒泡排序
for (int j = 0; j < i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
swap(b[j], b[j + 1]);
}
}
for (int i = 0; i < n; i++)
cout << b[i] << endl;
return 0;
}字符串中最长的连续出现的字符
求一个字符串中最长的连续出现的字符,输出该字符及其出现次数。字符串中无空白字符(空格、回车和tab),如果这样的字符不止一个,则输出出现最早的字符。
时间限制:1000
内存限制:65536
输入
一行,一个不包含空白字符的字符串,字符串长度小于200。
输出
一行,输出最长的连续出现的字符及其最长的连续出现次数,中间以一个空格分开。
样例输入
aaaaadbbbbbcccccccdddddddddd
样例输出
d 10
#include <iostream>
using namespace std;
int main() {
string s;
int n = 1, maxn = 1;
char maxc;
cin >> s;
int len = s.size(); // 字符串长度
maxc = s[0];
for (int i = 1; i < len; i++) {
if (s[i] == s[i - 1]) { // 与前一个字符相同,将n累加
n++;
if (n > maxn) { // 当前字符连续出现次数超过存储的最大值
maxn = n;
maxc = s[i];
}
} else
n = 1;
}
cout << maxc << " " << maxn;
return 0;
}公共子序列
我们称序列Z = < z1, z2, ..., zk >是序列X = < x1, x2, ..., xm >的子序列当且仅当存在 严格上升 的序列< i1, i2, ..., ik >,使得对j = 1, 2, ... ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b, c, f, b, c >的子序列。 现在给出两个序列X和Y,你的任务是找到X和Y的最大公共子序列,也就是说要找到一个最长的序列Z,使得Z既是X的子序列也是Y的子序列。
时间限制:3000
内存限制:65536
输入
输入包括多组测试数据。每组数据包括一行,给出两个长度不超过200的字符串,表示两个序列。两个字符串之间由若干个空格隔开。
输出
对每组输入数据,输出一行,给出两个序列的最大公共子序列的长度。
样例输入
abcfbc abfcab programming contest abcd mnp
样例输出
4 2 0
#include <bits/stdc++.h>
#include <string>
using namespace std;
int f[1000][1000];
int main() {
string a, b;
while (cin >> a >> b) {
int n = a.size();
int m = b.size();
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= m; k++) {
if (a[i - 1] == b[k - 1]) {
f[i][k] = max(f[i][k], f[i - 1][k - 1] + 1);
} else {
f[i][k] = max(f[i][k - 1], f[i - 1][k]);
}
}
}
cout << f[n][m] << endl;
}
return 0;
}硬币问题
有N(不大于100)种硬币,编号为1至N,已知每种硬币的重量(不超过100的正整数)和面额(不超过100的正整数),每种硬币数量不限。选取总重量不超过C(不大于1000的正整数)的硬币,最多能获得多少总面额?
时间限制:1000
内存限制:65536
输入
第一行输入N 第二行输入C 第三行输入各硬币重量,用空格隔开 第四行输入各硬币价值,用空格隔开
输出
最大总面额
样例输入
3 5 1 2 5 1 3 6
样例输出
7
#include <bits/stdc++.h>
using namespace std;
int t[105], v[105];
int dp[1005];
int main() {
int n, c;
cin >> n >> c;
for (int i = 1; i <= n; i++)
cin >> t[i];
for (int i = 1; i <= n; i++)
cin >> v[i];
for (int i = 1; i <= n; i++) {
for (int j = t[i]; j <= c; j++) {
dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
}
}
cout << dp[c];
return 0;
}田忌赛马
你一定听过田忌赛马的故事吧?
如果3匹马变成1000匹,齐王仍然让他的马按从优到劣的顺序出赛,田忌可以按任意顺序选择他的赛马出赛。赢一局,田忌可以得到200两银子,输一局,田忌就要输掉200两银子,平局的话不输不赢。
请问田忌最多能赢多少银子?
时间限制:5000
内存限制:65536
输入
输入包含多组测试数据. 每组测试数据的第一行是一个整数n(1<=n<=1000),表示田忌和齐王都拥有n匹马。接下来一行是n个整数,表示田忌的马的速度,下一行也是n个整数,表示齐王的马的速度。 输入的最后以一个0表示结束。
输出
对每组数据,输出一个整数,表示田忌至多可以赢多少银子,如果田忌赢不了,就输出一个负数,表示田忌最少要输多少银子。
样例输入
3 92 83 71 95 87 74 2 20 20 20 20 2 20 19 22 18 0
样例输出
200 0 0
#include <bits/stdc++.h>
using namespace std;
int h1, h2, t1, t2, n, i, ans = 0;
int t[100001], k[100001];
int cmp(int a, int b) { return a > b; }
int main() {
while (cin >> n && n) {
for (i = 1; i <= n; i++)
cin >> t[i];
for (i = 1; i <= n; i++)
cin >> k[i];
sort(t + 1, t + n + 1, cmp);
sort(k + 1, k + n + 1, cmp);
h1 = h2 = 1;
t1 = t2 = n;
while (h1 <= t1) {
if (t[h1] > k[h2])
ans += 200, h1++, h2++;
else {
if (t[h1] < k[h2])
ans -= 200, t1--, h2++;
else {
if (t[t1] > k[t2])
ans += 200, t1--, t2--;
else {
if (t[t1] < k[h2])
ans -= 200;
t1--, h2++;
}
}
}
}
cout << ans << endl;
ans = 0;
}
}上机
又到周末了,同学们陆陆续续开开心心的来到机房上机。jbr也不例外,但是他到的有点晚,发现有些机位上已经有同学正在做题,有些机位还空着。细心的jbr发现,一位同学来到机房,坐在机位i上,如果他的左右两边都空着,他将获得能力值a[i];如果当他坐下时,左边或者右边已经有一个人在上机了,他将获得能力值b[i];如果当他坐下时,他的左边右边都有人在上机,他将获得能力值c[i]。
同时他发现,已经在上机的同学不会受到刚要坐下的同学的影响,即他们的能力值只会在坐下时产生,以后不会发生变化;第一个机位左边没有机位,最后一个机位右边没有机位,无论何时坐在这两个机位上将无法获得c值。
这时jbr发现有一排机器还空着,一共有N个机位,编号1到N。这时有N位同学们陆陆续续来到机房,一个一个按照顺序坐在这排机位上。聪明的jbr想知道怎么安排座位的顺序,可以使这N位同学获得能力值的和最大呢?
时间限制:1000
内存限制:65536
输入
第一行一个整数N(1<= N <= 10000)
第二行N个数,表示a[i]
第三行N个数,表示b[i]
第四行N个数,表示c[i]
(1<= a[i],b[i],c[i] <=10000)
输出
一个整数,表示获得最大的能力值和
样例输入
4 1 2 2 4 4 3 3 1 2 1 1 2
样例输出
14
提示
第一位同学坐在第四个机位上,获得能力值4; 第二位同学坐在第三个机位上,获得能力值3; 第三位同学坐在第二个机位上,获得能力值3; 第四位同学坐在第一个机位上,获得能力值4; 总和为14。
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
int a[10005];
int b[10005];
int c[10005];
int d
[10005]
[4]; // 考虑前i的座位已经坐好的前i个座位最大值,0-第i个人坐下的时候两边没人,1-左边有人,2-右边有人,3-都有人
int main() {
int n;
cin >> n;
int i;
for (i = 1; i <= n; i++)
cin >> a[i];
for (i = 1; i <= n; i++)
cin >> b[i];
for (i = 1; i <= n; i++)
cin >> c[i];
d[1][0] = a[1];
d[1][2] = b[1];
for (i = 2; i <= n; i++) {
d[i][0] =
max(d[i - 1][3], d[i - 1][2]) +
a[i]; // 第i个位置坐下的时候两边没人,要求它先于第i-1个人被坐,也就是说第i-1个人坐下的时候一定是右边有人
d[i][1] = max(d[i - 1][0], d[i - 1][1]) + b[i];
d[i][2] = max(d[i - 1][3], d[i - 1][2]) + b[i];
d[i][3] = max(d[i - 1][0], d[i - 1][1]) + c[i];
}
cout << max(d[n][0], d[n][1]);
return 0;
}// 参考答案2
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 10000 + 1;
int a[N], b[N], c[N], dp[N][4];
int main() {
int n;
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]);
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
dp[1][0] = a[1];
dp[1][1] = -INF;
dp[1][2] = b[1];
dp[1][3] = -INF;
for (int i = 2; i <= n; i++) {
dp[i][0] = a[i] + max(dp[i - 1][2], dp[i - 1][3]);
dp[i][1] = b[i] + max(dp[i - 1][0], dp[i - 1][1]);
dp[i][2] = b[i] + max(dp[i - 1][2], dp[i - 1][3]);
dp[i][3] = c[i] + max(dp[i - 1][0], dp[i - 1][1]);
}
printf("%d\n", max(dp[n][0], dp[n][1]));
return 0;
}制作蛋糕
小A擅长制作香蕉蛋糕和巧克力蛋糕。制作一个香蕉蛋糕需要2个单位的香蕉,250个单位的面粉,75个单位的糖,100个单位的黄油。制作一个巧克力蛋糕需要75个单位的可可粉,200个单位的面粉,150个单位的糖,150个单位的黄油。一个香蕉蛋糕可以卖出400元,而一个巧克力蛋糕可以卖出450元。为了避免蛋糕变质,每种蛋糕至多只能制作100个。
现已知每种原料的数量,求小A至多可以卖出多少元的蛋糕。
时间限制:1000
内存限制:65536
输入
依次输入面粉、香蕉、糖、黄油、可可粉的数量,每种原料数量均为不超过100000的整数。
输出
输出一个整数,表示最多卖出的钱数。
样例输入
4000 6 2000 500 500
样例输出
1700
#include <bits/stdc++.h>
using namespace std;
int main() {
int mf, xj, t, hy, kkf, xjcake = 0, kkcake = 0, msum = 0, sum = 0;
cin >> mf >> xj >> t >> hy >> kkf;
for (int i = 0; i <= xj / 2; i++)
for (int j = 0; j <= kkf / 75; j++) {
if ((i * 250 + j * 200) <= mf && (i * 75 + j * 150) <= t &&
(i * 100 + j * 150) <= hy && i <= 100 && j <= 100) {
sum = i * 400 + j * 450;
if (sum > msum)
msum = sum;
}
}
cout << msum;
return 0;
}