学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4341

题目大意：小学在4399玩的这游戏。。。就是说在规定时间内，取最多的金子。告诉你每个金子取回来的时间跟位置。

解法：

首先我们可以知道，你在原点处，要勾金子，必然是一条直线下去，如果两块金子斜率相等，你肯定要先把近的那块勾起才能勾远的那块。所以这就相当于背包九讲的一种依赖关系，所以斜率相等的金子可以看成一个物品组，如，1 2 3 4块金子的斜率相等，并且距离递增。那么，我们把这四块放一个组里，DP时，只能取一个，为什么会只能一个？因为如果你要取4，实际上就是1 2 3 4全取了，你只要把第四块金子的价值跟时间把前面几块的都加上就可以了。然后就是分组，然后模板伺候、、、

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=250;
struct node
{
    int x,y,c,v;
    bool operator < (const node &a) const {
        return (y*a.x<a.y*x)||(y*a.x==a.y*x && x*x+y*y<a.x*a.x+a.y*a.y);
        /*斜率优先，斜率相等距离优先*/
    }
}t[maxn];

int n,V;
int dp[41000];

int solve ()
{
    int len=0,ans=0;;
    /*分组*/
    vector <node> group[maxn];
    memset(group,0,sizeof(group));
    group[len].push_back(t[0]);
    int pre=0;
    for(int i=1;i<n;i++)
    {
        if(t[pre].y*t[i].x==t[i].y*t[pre].x){
            t[i].c+=t[pre].c;
            t[i].v+=t[pre].v;
            group[len].push_back(t[i]);
        }
        else{
            group[++len].push_back(t[i]);
        }
        pre=i;
    }
    /*DP*/
    memset(dp,0,sizeof(dp));
    for(int i=0;i<=len;i++)
        for(int j=V;j>=0;j--)
            for(int l=0;l<group[i].size();l++)
                if(j>=group[i][l].c) dp[j]=max(dp[j],dp[j-group[i][l].c]+group[i][l].v);
    return dp[V];
}

int main()
{
    int T=1;
    while (scanf("%d %d",&n,&V)==2)
    {
        for(int i=0;i<n;i++)
            scanf("%d %d %d %d",&t[i].x,&t[i].y,&t[i].c,&t[i].v);
        sort(t,t+n);
        printf("Case %d: %d\n",T++,solve());
    }
    return 0;
}