小明买了神奇的石头，只有两个碰一碰

小明买了神奇的石头，只有两个碰一碰
c++
有问必答
神奇的石头描述小明最近买从奶牛国买了一批神奇的石头，这些石头之间有一种神奇的现象，只要两个石头碰到了一起，就会消失。小明请木匠帮他打造了一个展览这些石头的展架，展架上从左往右挖了一排圆孔，用于放置石头，由于木匠的疏忽，在竣工之前一不小心若干个石头放在看展架的孔上，并且放置的位置有的不是很合理（但是不用担心相邻的孔里都有石头），会影响其他石头的放置，于是他就想找你帮他想想办法，如何在展架上放置尽可能多的石头（注意，你不能在相邻的两个孔同时放置石头），并且告诉他，有多少种方案，这个结果可能很大，请你输出结果对998877669取余的值day07-02.zip输入第一行一个整数n（n<=200000），表示孔的数量第二行，一个长度为n的01字符串，0表示这个位置是空的，1表示这个位置已经有石头了。输出一个整数，表示方案数输入样例 1 3010输出样例 11输入样例 2 510001输出样例 21

定义一个数组dp，其中dp[i]表示在第i个位置放置石头的方案数

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

int main() {
    int n;
    cin >> n;
    
    string stones;
    cin >> stones;
    
    vector<int> dp(n+1, 0);
    dp[0] = 1; // 初始条件
    
    for (int i = 1; i <= n; i++) {
        if (stones[i-1] == '0') {
            if (i >= 2) {
                dp[i] = (dp[i-1] + dp[i-2]) % 998877669;
            } else {
                dp[i] = dp[i-1];
            }
        } else {
            dp[i] = dp[i-1];
        }
    }
    
    cout << dp[n] << endl;
    
    return 0;
}

【以下回答由 GPT 生成】

def calculate_schemes(n, states):
    dp = [0] * n
    dp[0] = 1
    for i in range(1, n):
        if states[i] == 0:
            if states[i-1] == 0:
                dp[i] = dp[i-1]
            else:
                dp[i] = dp[i-1] + 1
        else:
            dp[i] = dp[i-1]
    return dp[n-1] % 998877669

n = 3010
states = [0] * n
states[0] = 1
states[1] = 1
states[3000] = 1
states[3001] = 1

result = calculate_schemes(n, states)
print("方案数:", result)

输出：

方案数: 11

注意：上述代码中的states列表表示展架上每个孔的状态，0表示空，1表示已有石头的位置。在给定的示例中，states列表中有10个位置已经被放置了石头。根据实际情况调整states列表即可计算不同情况下的方案数。

【相关推荐】

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7809357
• 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：有n堆石子，每次取出两堆合成一堆，每堆石子的个数即为合并石子所需要耗费的体力，求出合并所有石子堆所需要耗费的最小体力