练习题 有奖问答

题目

问题描述

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

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

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

答案提交

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

运行限制

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	2s	256M
Python3	3s	256M
PyPy3	3s	256M
Go	3s	256M
JavaScript	3s	256M

提交代码

提交代码1（尝试）

//有奖问答//每道题有2种状态：对和不对
//答对可继续答，答错也可以继续答
//可以主动提前停止答题
//共30题
//每题10分
//实际得了70分
//求可能的答题情况有多少种
//填空题 
//答错分数归零 
//递归树
//广度优先遍历
//队列 
//出队一个节点，入队两个节点 
//达到100分停止 #include<iostream>
#include<queue>
using namespace std;struct Question{int num;//题目编号int score;//前num道题的分数 
};//问题结构体 int result = 0;//结果
queue<Question> q;//存储所有可能的分数 //广度优先搜索
void bfs(){Question ques;int i;//节点号int sum;//前i道题的总分数 while(!q.empty()){i = q.front().num;sum = q.front().score;//出队q.pop();//判断是否还有节点入队if(i < 30){ques.num = i + 1;//答对 ques.score = sum + 10;//入队时判断if(ques.score == 70){result++;}//入队if(ques.score != 100){q.push(ques);}//答错ques.score = 0;if(ques.score == 70){result++;}//入队 if(ques.score != 100){q.push(ques);} }else{break;}}
} int main(){//队列中放入初始节点q.push(Question{0,0});//BFSbfs();//输出结果printf("%d",result); return 0;
}

解题思路：画出递归树，每一道题都可能答对或答错，即每一道题都有两种状态，可以使用广度优先遍历，一道题一道题看，这一道题基于前面所有题的答题情况再加两种。但是会超时。

提交代码2

//有奖问答//每道题有2种状态：对和不对
//答对可继续答，答错也可以继续答
//可以主动提前停止答题
//共30题
//每题10分
//实际得了70分
//求可能的答题情况有多少种
//填空题 
//答错分数归零 
//动态规划 
//达到100分停止 #include<iostream>
using namespace std;int result = 0;//结果
int dp[31][31];//dp[i][j]：到第i题，累计获得j*10分 int main(){//初始条件 dp[0][0] = 0;dp[1][0] = 1;dp[1][1] = 1;int sum = dp[1][0] + dp[1][1];//到上一道题结束后共可能有多少种情况for(int i = 2;i < 31;i++){//答对10题自动结束 for(int j = 0;j <= i && j <= 10;j++){if(j == 0){//当前这道题错了dp[i][j] = sum;//上一道题所有情况之和}else{dp[i][j] = dp[i - 1][j - 1];//到上一题做完最多只能做完9题if(j != 10){sum += dp[i][j];} if(j == 7){result += dp[i][j];}}//printf("%d ",dp[i][j]);}//printf("\n");} //输出结果printf("%d",result); return 0;
}

解题思路：题目明显存在两种状态，适合使用动态规划，用空间换时间。将大问题拆分成做到哪一道问题这种小问题，每种小问题又根据得了多少分划分成更小的问题，每种情况存储的就是可能的情况数，即dp[i][j]表示做完第i题共得了j*10分时可能的答题情况有多少种，除了dp[i][0]是dp[i-1][0]+dp[i-1][1]+...dp[i-1][min(i-1,9)]，其余的dp[i][j]=dp[i-1][j-1]。