用C++写一个 收益最大化 有n个格子，每个格子里放着不定价值的金币。你可以拿走格子里的金币，但是不能连续拿两个格子里的金币。 请给出最多能拿走多少价值的金币。 输入说明： 第一行输入格子的个数n 第二行依次输入每个格子里的金币价值 输入说明： 最多能拿走多少价值的金币 输入示例： 4 1 2 3 1 输出示例： 4

好的，下面是 C++ 的实现代码：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> value(n);
    for (int i = 0; i < n; i++) {
        cin >> value[i];
    }

    vector<int> dp(n + 1);
    dp[1] = value[0];

    for (int i = 2; i <= n; i++) {
        dp[i] = max(dp[i-1], dp[i-2] + value[i-1]);
    }

    cout << dp[n] << endl;
    return 0;
}

输入样例：

4
1 2 3 1

输出样例：

4

相关问题

K15887 正方形（sqr） (100分) 题目描述 求一个n行m列的矩形网格中，包括多少个正方形（每个格子都是完全相同的小正方形格子）。 如2*3的矩形网格中，边长为1的正方形有6个，边长为2的正方形有2个，共包括8个正方形。c++入门代码怎么写

K15887 的题目要求计算给定大小的矩阵中所有可能存在的正方形的数量。正方形的边长可以是1到n*m之间的任意整数。为了求解这个问题，你可以采用动态规划的方法。以下是简单的 C++ 入门代码示例：

#include <iostream>
using namespace std;

int countSquares(int n, int m) {
    // 初始化一个二维数组来存储每个位置上最大包含的正方形边长
    int dp[n][m];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            // 如果当前位置是边界，则最多能形成边长为1的正方形
            if (i == 0 || j == 0 || i == n - 1 || j == m - 1)
                dp[i][j] = 1;
            else {
                // 否则，dp[i][j]等于它上面、左面以及对角线上的较小边长加1
                dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
    }

    int total = 0;
    // 计算并累加所有正方形的数量
    for (int k = 1; k <= n && k <= m; ++k) {
        total += (n - k + 1) * (m - k + 1);
    }

    return total;
}

int main() {
    int n, m;
    cout << "请输入矩阵的行数和列数: ";
    cin >> n >> m;
    cout << "该矩阵中共有 " << countSquares(n, m) << " 个正方形。" << endl;
    return 0;
}

这个程序首先初始化一个动态规划表 `dp`，然后通过遍历每个单元格，更新其能够形成的正方形的最大边长。最后，统计所有可能的边长，乘以其对应的面积（`(n-k+1)*(m-k+1)`），并将它们加起来得到总正方形数。

摆摊地图，二维矩阵，每个格子0或1,，1可摆摊，0不可摆摊，相邻格子不可同时摆摊，问有多少种摆摊方案C++笔试代码

以下是一个基于回溯算法的C++代码示例，可以用于求解摆摊地图问题：

#include <iostream>
using namespace std;

const int MAXN = 20;  // 最大地图大小
int n, m;            // 地图的大小
int map[MAXN][MAXN]; // 地图
bool vis[MAXN][MAXN]; // 标记每个格子是否已经被访问过
int cnt;             // 摆摊方案的数量

// 判断当前格子是否可以摆摊
bool check(int x, int y) {
    // 如果当前格子已经被访问过，或者不能摆摊，返回false
    if (vis[x][y] || map[x][y] == 0) {
        return false;
    }
    // 检查当前格子的上、下、左、右四个方向是否已经被摆摊
    if ((x > 0 && vis[x-1][y]) || (x < n-1 && vis[x+1][y]) ||
        (y > 0 && vis[x][y-1]) || (y < m-1 && vis[x][y+1])) {
        return false;
    }
    return true;
}

// 搜索所有可能的摆摊方案
void dfs(int x, int y) {
    // 如果已经遍历完整个地图，表示找到了一种方案
    if (x == n) {
        cnt++;
        return;
    }
    // 计算下一个格子的坐标
    int nx = y == m-1 ? x+1 : x;
    int ny = y == m-1 ? 0 : y+1;
    // 如果当前格子可以摆摊，尝试摆摊并继续遍历下一个格子
    if (check(x, y)) {
        vis[x][y] = true;
        dfs(nx, ny);
        vis[x][y] = false;
    }
    // 尝试不摆摊并继续遍历下一个格子
    dfs(nx, ny);
}

int main() {
    // 读入地图大小和每个格子的信息
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    // 初始化摆摊方案数量为0，并从左上角开始搜索
    cnt = 0;
    dfs(0, 0);
    // 输出结果
    cout << cnt << endl;
    return 0;
}

该代码使用了一个二维数组`vis`来标记每个格子是否已经被访问过，以及一个变量`cnt`来记录摆摊方案的数量。在`dfs`函数中，首先判断当前格子是否可以摆摊，如果可以，则尝试将该格子标记为已摆摊，并继续搜索下一个格子。如果不可以，则直接搜索下一个格子。在搜索完整个地图后，`cnt`中的值就是摆摊方案的总数。

需要注意的是，该算法的时间复杂度为$O(2^{n\times m})$，对于较大的地图，可能会超时。因此，可以使用一些优化技巧来减少搜索空间，例如剪枝、启发式搜索等。