今天的题目也是来自洛谷的一道提高+/省选-题，我发现这个难度大概和leetcode中困难差不多。这题一眼看过去就知道是一道树形背包，虽然看题解里有人说用退火模拟也可以写，但是我不会。而且这题看起来就和之前写过的那些树形背包的裸体一样，甚至还要更简单一点，这种有依赖的背包而且，每一个结点都只有一个子树的，最简单的方法就是直接把每一个状态都划分出来，将叶结点N以及所有的父节点都划分为一个物品，重量为当前节点到根节点的重量和，价值也是价值和，这样这个问题就转化成了朴素的分组背包，直接循环结束就可以了。
但是这题有点困难的地方在于，虽然解法简单，但是这题给出的数据是坐标系，你需要根据到原点的斜率判断是不是在一条线上来确定结点的父子关系。处理方法有很多，例如x1*y2=x2*y1或者x/gcd(x,y),y/gcd(x,y)还有可以直接储存斜率，因为数据范围是200整数，所以不会有浮点数误差？反正我第一时间没敢用这种方法，不过好像也是可以的。还有就是因为x的坐标可能为负，映射时需要用map或者在数组下标添加一个位移。
#include<bits/stdc++.h>
using namespace std;
const int N=210;
int cnt = 0;
int mapz[N*2][N];
int dp[40010];
struct node{
int x,y,t,v;
// double k;
};
vector<node> tree[N];
int gcd(int a, int b){
if(a%b == 0)return b;
gcd(b,a%b);
// return 0;
}
int main(void){
int n , t;cin>>n>>t;
for(int i = 0 ; i < n ; i ++){
int x,y,t,v;cin>>x>>y>>t>>v;
int flag = 0;
if(x<0){x = -x;flag = 1;}
int k = gcd(x,y);
int a,b;
if(flag==0){a = x/k;b=y/k;}
else {a =x/k+201;b=y/k;}
if(mapz[a][b] == 0){
mapz[a][b] = ++cnt;
}
tree[mapz[a][b]].emplace_back(node {x,y,t,v});
// cout<<mapz[a][b]<<" "<<tree[mapz[a][b]].size()<<endl;
}
for(int i = 1 ; i <= cnt ; i ++){
// cout<<tree[i].size()<<endl;
sort(tree[i].begin(),tree[i].end(),[](node a,node b){return b.y>a.y;});
for(int j = 1 ; j < tree[i].size() ; j ++){
tree[i][j].t += tree[i][j-1].t;
tree[i][j].v +=tree[i][j-1].v;
// cout<<tree[i][j].t<<endl;
}
for(int j = t ; j>=tree[i][0].t ; j --){
for(int k = tree[i].size()-1 ; k >= 0 ; k--){
if(j>=tree[i][k].t)dp[j] = max(dp[j],dp[j-tree[i][k].t]+tree[i][k].v);
}
}
}
cout<<dp[t];
return 0;
}