百度之星 初赛 1 - GPA

一开始大家都没有想到，因为分布是不均匀的，所以这其实不是贪心。比如180的情况，最赚的是3.0。有点像背包，但也有点不一样。

考虑DP，状态转移方程的核心在于枚举：把总分拆出来多少分，作为单独的一门课的成绩。

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &(x))
#define pr(x) printf("%.1lf\n", (x))
using namespace std;
int a[] = {0, 0, 60, 62, 65, 67, 70, 75, 80, 85, 90, 95};
double b[] = {0, 0, 1.0, 1.7, 2.0, 2.3, 2.7, 3.0, 3.3, 3.7, 4.0, 4.3};
double deal(int x) {
    int i;
    for (i = 1; i <= 11; ++i) {
        if (a[i] > x) break;
    }
    return b[i - 1];
}
double dp[401];
int main() {
    for (int i = 0; i <= 400; ++i)
        for (int j = i - 1; j >= 0; --j)
            dp[i] = max(dp[i], deal(i - j) + dp[j]);
    int n, T;
    sc(T);
    while (T--) {
        sc(n);
        pr(dp[n]);
    }
    return 0;
}

可以在此基础上进行常数优化，虽然比赛的时候我是打表的

#include <bits/stdc++.h>
#define sc(x) scanf("%d", &(x))
#define pr(x) printf("%.1lf\n", (x))
using namespace std;
int a[] = {0, 0, 60, 62, 65, 67, 70, 75, 80, 85, 90, 95};
double b[] = {0, 0, 1.0, 1.7, 2.0, 2.3, 2.7, 3.0, 3.3, 3.7, 4.0, 4.3};
double deal(int x) {
    int i;
    for (i = 1; i <= 11; ++i) {
        if (a[i] > x) break;
    }
    return b[i - 1];
}
double dp[401];
int main() {
    for (int i = 0; i <= 400; ++i)
        for (int j = i - 1; j >= 0 && i - j <= 95; --j)//常数优化
            dp[i] = max(dp[i], deal(i - j) + dp[j]);
    int n, T;
    sc(T);
    while (T--) {
        sc(n);
        pr(dp[n]);
    }
    return 0;
}