23年蓝桥杯省赛A组填空题：有奖问答 C++动态规划题解_蓝桥杯有奖问答

原题链接：用户登录https://www.lanqiao.cn/problems/3497/learning/?subject_code=1&group_code=5&match_num=14&match_flow=1&origin=cup

题目描述：

小蓝正在参与一个现场问答的节目。活动中一共有 3030 道题目, 每题只有答对和答错两种情况, 每答对一题得 1010 分，答错一题分数归零。

小蓝可以在任意时刻结束答题并获得目前分数对应的奖项，之后不能再答任何题目。最高奖项需要 100100 分, 所以到达 100100 分时小蓝会直接停止答题。请注意小蓝也可能在不到 100100 分时停止答题。

已知小蓝最终实际获得了 7070 分对应的奖项, 请问小蓝所有可能的答题情况有多少种?

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

运行限制

总通过次数: 818  |  总提交次数: 954  |  通过率: 85.7%

难度: 困难   标签: 2023, 省赛, 动态规划, DP

思路：

首先知道，

第一次得10分的情况数有1，第一次得0分的情况数也有1

我们穷举三十次答题，每次答题时的不同分数（注意不是得分，是当时的分数）的情况，根据每次得分不同，执行不同的操作。

for (int i = 2; i <= 30; i++)
    for (int j = 0; j <= 90; j += 10) { //这里不枚举到100的原因是，这种情况不存在，因为是以70分结束的，100分一定会结束，而80，90分不一定结束
        if (j == 0) {
            //第i题未做对，方案数为做完第i-1题所有方案数之和 
            for (int k = 0; k <= 90; k += 10)
                dp[i][0] += dp[i - 1][k];
        }
        else {
            dp[i][j] = dp[i - 1][j - 10];  //第i题做对 
            if (j == 70) res += dp[i][j];
        }

如果我们在大循环里加入这条语句：
cout <<i<<"次" << j <<"分" << endl;

就能看到我们遍历的是什么了：

完整代码：

#include <iostream>
#include <cstring>
using namespace std;
int dp[31][100];  //dp[i][j]表示做完第i题，得分为j的方案数
int main() {
 
    int res = 0;
    dp[1][0] = dp[1][10] = 1;
    for (int i = 2; i <= 30; i++)
        for (int j = 0; j <= 90; j += 10) { //这里不枚举到100的原因是，这种情况不存在，因为是以70分结束的，100分一定会结束，而80，90分不一定结束
            if (j == 0) {
                //第i题未做对，方案数为做完第i-1题所有方案数之和 
                for (int k = 0; k <= 90; k += 10)
                    dp[i][0] += dp[i - 1][k];
            }
            else {
                dp[i][j] = dp[i - 1][j - 10];  //第i题做对 
                if (j == 70) res += dp[i][j];
            }
            
        }
    cout << res;
    return 0;
}