HDU 4341 判断共线+背包

题意：黄金矿工的意思，每个点有价值和时间，如果共线得从最近的开始取，问求时间t內取到的最大价值。

这题把共线的情况看成一组，要取某个点的话必须把跟这个点共线并且与原点距离在这个点之前的点取到。所以把每条线上的分组用分组背包就可以了。

#include <iostream>
#include<cstring>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct point
{
    int x,y,t,v,a;
};
int Direction(point pi,point pj,point pk) //判断向量PiPj在向量PiPk的顺逆时针方向 +顺-逆0共线
{
    return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
int dis(point a,point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
point o;
bool cmp(point a,point b)
{
    return dis(a,o)<dis(b,o);
}
int ans[2][40005];
int main()
{
    int n,t,g1,g2,ca=0;
    point data[205],now[205];
    o.x=o.y=0;
    while(~scanf("%d%d",&n,&t))
    {
        g1=0,g2=1;
        memset(ans,0,sizeof(ans));
        for(int i=0; i<n; i++)
            scanf("%d%d%d%d",&data[i].x,&data[i].y,&data[i].t,&data[i].v),data[i].a=-1;
        for(int i=0; i<n; i++)
            if(data[i].a==-1)
            {
                data[i].a=i;
                now[0]=data[i];
                int num=1;
                for(int j=i+1; j<n; j++)
                    if(Direction(data[i],data[j],o)==0)
                        data[j].a=i,now[num++]=data[j];
                sort(now,now+num,cmp);
                for(int j=1; j<num; j++)
                    now[j].t+=now[j-1].t,now[j].v+=now[j-1].v;
                swap(g1,g2);
                for(int j=0; j<=t; j++) ans[g2][j]=ans[g1][j];
                for(int j=0; j<num; j++)
                    if(now[j].v>ans[g2][now[j].t]&&now[j].t<=t)
                        ans[g2][now[j].t]=now[j].v;
                for(int j=0; j<=t; j++)
                    if(ans[g1][j]||j==0)
                        for(int k=0; k<num; k++)
                            if(j+now[k].t<=t&&ans[g1][j]+now[k].v>ans[g2][j+now[k].t])
                                ans[g2][j+now[k].t]=ans[g1][j]+now[k].v;
            }
        int mans=0;
        for(int i=t; i>=0; i--)
            mans=max(mans,ans[g2][i]);
        printf("Case %d: %d\n",++ca,mans);
    }
    return 0;
}