hdu 4972 A simple dynamic programming problem(高效)

本文主要是介绍hdu 4972 A simple dynamic programming problem(高效)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：hdu 4972 A simple dynamic programming problem

题目大意：两支球队进行篮球比赛，每进一次球后更新比分牌，比分牌的计数方法是记录两队比分差的绝对值，每次进球的分可能是1，2，3分。给定比赛中的计分情况，问说最后比分有多少种情况。

解题思路：分类讨论：

• 相邻计分为1-2或者2-1的时候，会对应有两种的的分情况
• 相邻计分之差大于3或者说相等并且不等于1的话，为非法输入
• 其他情况下，不会造成新的比分情况产生
• 对于最后一次比分差为0的情况，就没有谁赢谁输一说。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 1e5+5;int N, a[maxn];int solve () {int cnt = 1;for (int i = 1; i <= N; i++) {if (a[i] == 1 && a[i-1] == 2)cnt++;else if (a[i] == 2 && a[i-1] == 1)cnt++;else if (a[i] - a[i-1] > 3 || a[i-1] - a[i] > 3)return 0;else if (a[i] == a[i-1] && a[i] != 1)return 0;}if (a[N] == 0)return cnt;elsereturn cnt * 2;
}int main () {int cas;scanf("%d", &cas);for (int kcas = 1; kcas <= cas; kcas++) {scanf("%d", &N);for (int i = 1; i <= N; i++)scanf("%d", &a[i]);printf("Case #%d: %d\n", kcas, solve());}return 0;
}

这篇关于hdu 4972 A simple dynamic programming problem(高效)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---