题意：
从（0，0）点取黄金，黄金的坐标破（x，y），取这个黄金所需时间t，价值v，在与原点同一条连线上的黄金需要先取最近的才能取后面的，求T时间内能获得的最大价值
dp：
首先预处理，求出每个点与原点连线的斜率，按斜率和与原点距离从小到大排序，把斜率相同的点分为一组，预处理出这一组选i个物品所需时间与所得价值，再分组背包dp即可
时间复杂度：
O（nt）
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 #define db double 5 struct node 6 { 7 int x,y,t,v; 8 db k; 9 }a[2005]; 10 bool cmp(node x,node y) 11 { 12 if(x.k == y.k)return x.y < y.y; 13 return x.k < y.k; 14 } 15 int N,T,cnt; 16 int num[2005],v[2005][2005],t[2005][2005]; 17 int f[40005]; 18 int main() 19 { 20 scanf("%d%d",&N,&T); 21 for(int i= 1;i <= N;i ++) 22 { 23 scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].t,&a[i].v); 24 a[i].k = (db)((db)a[i].y / (db)a[i].x); 25 } 26 sort(a + 1,a + 1 + N,cmp); 27 for(int i = 1;i <= N;i ++) 28 { 29 if(a[i].k != a[i - 1].k)cnt ++; 30 num[cnt]++;//如果不写在外面就会80？？？？？ 31 v[cnt][num[cnt]] = v[cnt][num[cnt] - 1] + a[i].v; 32 t[cnt][num[cnt]] = t[cnt][num[cnt] - 1] + a[i].t; 33 } 34 for(int i = 1;i <= cnt;i ++) 35 for(int j = T;j >= t[i][1];j --) 36 for(int k = 1;k <= num[i];k ++) 37 if(j >= t[i][k])f[j] = max(f[j],f[j - t[i][k]] + v[i][k]); 38 printf("%d\n",f[T]); 39 return 0; 40 }