首页 > 代码库 > HDU 4968 Improving the GPA(dp)
HDU 4968 Improving the GPA(dp)
HDU 4968 Improving the GPA
题目链接
dp,最大最小分别dp一次,dp[i][j]表示第i个人,还有j分的情况,分数可以减掉60最为状态
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int t, avg, n; double dp1[15][405], dp2[15][405]; double get(int x) { if (x >= 25 && x <= 40) return 4.0; if (x >= 20 && x <= 24) return 3.5; if (x >= 15 && x <= 19) return 3.0; if (x >= 10 && x <= 14) return 2.5; return 2.0; } void init() { for (int i = 1; i <= 400; i++) dp2[0][i] = 50; for (int i = 1; i <= 10; i++) { for (int j = 0; j <= 400; j++) { dp1[i][j] = 0; dp2[i][j] = 50; for (int k = 0; k <= j && k <= 40; k++) { dp1[i][j] = max(dp1[i][j], dp1[i - 1][j - k] + get(k)); dp2[i][j] = min(dp2[i][j], dp2[i - 1][j - k] + get(k)); } } } } int main() { init(); scanf("%d", &t); while (t--) { scanf("%d%d", &avg, &n); avg = (avg - 60) * n; printf("%.4lf %.4lf\n", dp2[n][avg] / n, dp1[n][avg] / n); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。