模块化网站开发,网站与数据库的联系,定制软件开发流程,wordpress首页不显示题目
问题描述
小蓝正在参与一个现场问答的节目。活动中一共有 3030 道题目, 每题只有答对和答错两种情况, 每答对一题得 10 分#xff0c;答错一题分数归零。
小蓝可以在任意时刻结束答题并获得目前分数对应的奖项#xff0c;之后不能再答任何题目。最高奖项需要 100 分,…题目
问题描述
小蓝正在参与一个现场问答的节目。活动中一共有 3030 道题目, 每题只有答对和答错两种情况, 每答对一题得 10 分答错一题分数归零。
小蓝可以在任意时刻结束答题并获得目前分数对应的奖项之后不能再答任何题目。最高奖项需要 100 分, 所以到达 100 分时小蓝会直接停止答题。请注意小蓝也可能在不到 100 分时停止答题。
已知小蓝最终实际获得了 7070 分对应的奖项, 请问小蓝所有可能的答题情况有多少种?
答案提交
这是一道结果填空的题你只需要算出结果后提交即可。本题的结果为一个整数在提交答案时只填写这个整数填写多余的内容将无法得分。
运行限制
语言最大运行时间最大运行内存C1s256MC1s256MJava2s256MPython33s256MPyPy33s256MGo3s256MJavaScript3s256M
提交代码
提交代码1尝试
//有奖问答//每道题有2种状态对和不对
//答对可继续答答错也可以继续答
//可以主动提前停止答题
//共30题
//每题10分
//实际得了70分
//求可能的答题情况有多少种
//填空题
//答错分数归零
//递归树
//广度优先遍历
//队列
//出队一个节点入队两个节点
//达到100分停止 #includeiostream
#includequeue
using namespace std;struct Question{int num;//题目编号int score;//前num道题的分数
};//问题结构体 int result 0;//结果
queueQuestion 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分停止 #includeiostream
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]。
