本文主要是介绍[Offer收割]编程练习赛2 hihocoder 1272 买零食 (DFS 或 dp 水题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
-
1 4 0.5 6 4.5 7 5.0 4 2.0 9 样例输出 -
17
描述
小Ho很喜欢在课间去小卖部买零食。然而不幸的是，这个学期他又有在一教的课，而一教的小卖部姐姐以冷若冰霜著称。第一次去一教小卖部买零食的时候，小Ho由于不懂事买了好一大堆东西，被小卖部姐姐给了一个“冷若冰霜”的眼神，食欲都下降了很多。
从那以后，小Ho就学乖了，去小卖部买东西只敢同时买3包以内的零食，并且价格加起来必须是5的整数倍，方便小卖部姐姐算价格。
但是小Ho不擅长计算，所以他把小卖部里所有零食的价格以及他对这个零食的渴望度都告诉了你，希望你能够帮他计算出在不惹恼小卖部姐姐的前提下，能够买到零食的渴望度之和最高是多少？
输入
每个输入文件包含多组测试数据，在每个输入文件的第一行为一个整数Q，表示测试数据的组数。
每组测试数据的第一行为一个正整数N，表示小卖部中零食的数量。
接下来的N行，每行为一个正实数A和一个正整数B，表示这种零食的价格和小Ho对其的渴望度。
一种零食仅有一包。
对于100%的数据，满足1 <= Q <= 10，1<=N<=50，0<A<=10，1<=B<=100。
对于100%的数据，满足A的小数部分仅可能为0.5或0。
输出
对于每组测试数据，输出一个整数Ans，表示小Ho可以获得最大的渴望度之和。
题目链接：http://hihocoder.com/problemset/problem/1273
题目分析：数据很小，随便搞，读入的时候把小数转整数，可避免精度问题
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int ans, n, cost[55], val[55];void DFS(int pos, int num, int p, int cnt)
{if(num && num % 50 == 0 && cnt <= 3)if(p > ans)ans = p;if(cnt > 3 || pos == n)return;DFS(pos + 1, num, p, cnt);DFS(pos + 1, num + cost[pos], p + val[pos], cnt + 1);
}int main()
{int T;scanf("%d", &T);while(T --){ans = 0;int tmp1;scanf("%d", &n);double tmp;for(int i = 0; i < n; i++){scanf("%lf", &tmp);cost[i] = (int) (tmp * 10.0);scanf("%d", &val[i]);}DFS(0, 0, 0, 0);printf("%d\n", ans);}
}这篇关于[Offer收割]编程练习赛2 hihocoder 1272 买零食 (DFS 或 dp 水题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
