首页 > 代码库 > HDU 4972 - A simple dynamic programming problem
HDU 4972 - A simple dynamic programming problem
题意：
给出一场篮球赛每次得分后的分差，求最终这场比赛的比分有多少种
分析：
因为知道了最终的分差，只需要考虑最终的得分之和有多少种，就能确定比分的种数
只有分差 1-2 或 2-1 能使总分的增量为 1 或 3. 其他情况只有一种增量
若 1-2 或 2-1 有 cnt 种，则最后比分之和有 cnt+1 种
若分差为 0 则没有先后之分，否则答案乘 2
考虑错误输入：
相邻分数之差大于3
相邻分数相等却不等于1
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 using namespace std; 5 const int N = 100005; 6 int t, n; 7 int a[N]; 8 int solve() 9 {10 int cnt = 1;11 for (int i = 1; i <= n; i++)12 {13 if (abs(a[i]-a[i-1]) > 3) return 0;14 if (a[i] == a[i-1] && a[i] != 1) return 0;15 if (a[i] == 1 && a[i-1] == 2 || a[i] == 2 && a[i-1] == 1) cnt++;16 }17 if (a[n] == 0) return cnt;18 else return cnt*2;19 }20 int main()21 {22 scanf("%d", &t);23 for (int tt = 1; tt <= t; tt++)24 {25 scanf("%d", &n);26 a[0] = 0;27 for (int i = 1; i <= n; i++) scanf("%d", &a[i]);28 printf("Case #%d: %d\n", tt, solve());29 }30 }
HDU 4972 - A simple dynamic programming problem
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。