0.题目
小蓝正在参与一个现场问答的节目。
活动中一共有 30 道题目,每题只有答对和答错两种情况,每答对一题得 10 分,答错一题分数归零。
小蓝可以在任意时刻结束答题并获得目前分数对应的奖项,之后不能再答任何题目。
最高奖项需要 100 分,所以到达 100 分时小蓝会直接停止答题。
已知小蓝最终实际获得了 70 分对应的奖项,请问小蓝所有可能的答题情况有多少种?
本题的结果为一个整数,在提交答案时只输出这个整数,输出多余的内容将无法得分。
1.题解
1.1 线性dp
思路
设置dp[i][j],其中i代表小蓝当前做了i题,j表示小蓝当前计分的题目数(分数 = j * 10)
注意:
1.小蓝可以在任意时刻结束答题并获得当前分数,所以我要计算出所有当分数
2.(j!=0) dp[i][j] = dp[i-1][j-1]; 如果当前j!=0,也就是不是归零的情况,从前一次,分数少一分的情况继承次数即可
(j0) dp[i][0] = dp[i-1][0-9];如果 j0, 说明遇到归零情况,所有分数全部归零,包含前一次所有情况,本次分数归零达到当前情况
3.注意到最高奖项100分,所以j的最大值设置为9,记录10是没有意义的,此时已经停止答题,不可能再遇到符合满70分的情况.
代码
#include<bits/stdc++.h>
using namespace std;
int dp[31][10];
int main() {
dp[0][0] = 1;
int ans = 0;
for (int i = 1; i <= 30; i++) {
for (int j = 0; j <= 9; j++) {
if(j) dp[i][j] = dp[i-1][j-1];
else {
for(int k = 0; k <= 9; k++) {
dp[i][j] += dp[i-1][k];
}
}
}
ans += dp[i][7];
}
cout << ans;
}
1.2 搜索
思路
代码
标签:分数,归零,答题,int,有奖,蓝桥,小蓝,2023,dp
From: https://www.cnblogs.com/trmbh12/p/18117530