365
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;
}
最後更新：2017-04-03 16:59:46