题目链接: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;
else
return 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 1022 Train Problem I 附详细思路
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...
A simple SDK for HDU. hdu-api 是一个集结 HDU 所有教务管理服务的 SDK,提供了一卡通服务、考试、课表、选课和一些公共信息如空闲教室、上课时间等信息的 API。 hdu-api 主要基于 Requests 库和 Beautiful Soup 库...
考试类精品--A simple SDK for HDU. 一个提供一卡通服务、考试、课表、选课和公共信息等 API
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。 现在,给你...
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
The first line of the input will contain a single integer indicating the number of problem instances. Each instance will consist of a single line of the form m n1 n2 n3 ... nm where m is the number ...
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
八数码的A*算法~不是很高效,但是很适合刚刚学这个算法的朋友们
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu_2102_passed_sorce
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)