HDU 4341 Gold miner 【思维 + 分组背包好题】

传送门
// 题意: 一个在(0, 0) 处抓金子, 对于每个金子都要它被抓到的时间和价值, 问在T时间内所能获得的最大价值是多少. 对于斜率相同的点只能先抓近的, 再抓远的.

// 思路：我们首先将所有的点按照斜率排序, 斜率相同的离原点近的在前面, 然后对于斜率相同的点, 我们把其分到一组, 假如6个点分组为(1) (2, 3) (4, 5, 6), 那么对于(2, 3)这个组, 我们将第2个点的时间和价值加到3上, 那么问题就变成了再分的组当中每一组最多选一个可以获得的最大价值, 那么就是分组背包了. 详见背包九讲….

注意就是分组那个的处理还是有些技巧性的, 我用的gr数组表示的, gr[i][0] 代表第i组中的个数, 然后gr[i][1-gr[i][0]] 代表没个金子的信息, 包括时间与价值. 然后常规做分组背包即可…

AC Code

const int maxn = 2e2+5;
struct node {
    int x, y, t, v;
    bool operator < (const node& _) const {
        if (y*_.x == x*_.y) return x*x+y*y < _.x*_.x+_.y*_.y;
        return y*_.x < x*_.y;
    }
}po[maxn];
int cas = 1;
int dp[maxn*maxn];
int gr[maxn][maxn];
int n, tot, m;
void work() {
    Fill(dp, 0);
    for (int k = 1 ; k <= m ; k ++)
        for (int i = tot ; i >= 0 ; i --)
            for (int j = 1 ; j <= gr[k][0] ; j ++)
                if (i>=po[gr[k][j]].t)
                    dp[i] = max(dp[i], dp[i-po[gr[k][j]].t] + po[gr[k][j]].v);

}
void solve()
{
    while(~scanf("%d%d", &n, &tot)) {
        for (int i = 1 ; i <= n ; i ++) {
            scanf("%d%d%d%d", &po[i].x, &po[i].y, &po[i].t, &po[i].v);
        }
        sort(po+1, po+1+n);
        m = 0;
        for (int i = 1 ; i <= n ; i ++) {
            int a = po[i].t;
            int b = po[i].v;
            gr[++m][0] = 0;
            gr[m][++gr[m][0]] = i;
            for (i++ ; i <= n ; i ++) {
                a += po[i].t;
                b += po[i].v;
                if (po[i-1].y*po[i].x == po[i-1].x*po[i].y) {
                    gr[m][++gr[m][0]] = i;
                    po[i].t = a;
                    po[i].v = b;
                }
                else {
                    --i;
                    break;
                }
            }
        }
        work();
        printf("Case %d: %d\n", cas++, dp[tot]);
    }
}