황금광부(dp)

제목은 황금 광부를 묘사하는 재미있는 광산 발굴 놀이이다.금광은 2차원 평면으로 볼 수 있다.유저는 원점(0,0)에 서서 밧줄을 아래로 보내고 채굴을 진행합니다.금광에는 금의 가치가 다른 것 외에 해골 같은 물건도 있다.유저는 한정된 시간 내에 채굴을 진행하여 자신의 수익을 최대화해야 한다.모든 물품은 x축 아래에 있습니다. (x, y)에 있는 물품에 대해 우리는 x2+y2의 시간이 필요합니다.그리고 만약에 두 개의 물품에 대해 그들의 위치는 각각 (x1, y1)과 (x2, y2)이고 y1/x1=y2/x2 및 |y1|금광에 n의 물품이 있는데 그들의 위치(x, y)와 가치, 그리고 게임의 제한 시간을 만족시키면 최대 수익이 얼마나 적은지 물어본다.
첫 번째 줄의 두 정수 n과 m를 입력하여 물품 수와 시한을 표시합니다.다음 n줄, 줄마다 아이템을 설명합니다.각 줄은 세 개의 정수, x, y와 c를 포함하여 각각 이 물품의 x, y 좌표와 가치를 나타낸다.
출력 출력 한 줄, 정수 포함 최대 수익
샘플 입력 3 16 1 - 1 - 2 2 - 28 - 2 - 3
샘플 출력 6
제시 50% 데이터, 1<=n<=15 100% 데이터, 1<=n<=100, -100<=x<=100, -100<=y<=-1, -10000<=c<=10000, 1<=m<=10000
사고방식은 한 직선의 물품에 대해 먼저 앞의 물품을 들고 뒤의 물품을 가져가야 하기 때문에 모든 경사율에 대해 이 경사율의 접두사와 모든 접두사와 dp를 계산하면 된다
코드 구현

#pragma GCC optimize(3,"Ofast","inline")
#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=105;
const int M=10005;
const int INF=0x3f3f3f;
const ull sed=31;
const ll mod=1e9+7;
const double eps=1e-9;
typedef pair<int,int>P;
typedef pair<double,double>Pd;
 
struct node
{
     
    int t,v,y;
    node(){
     }
    node(int _t,int _v):t(_t),v(_v){
     }
    node(int _t,int _v,int _y):t(_t),v(_v),y(_y){
     }
};
unordered_map<double,int>vis;
int n,m,cnt,dp[M];
vector<node>E[N];
int f[N][N][2];
bool cmp(node a,node b)
{
     
    return abs(a.y)<abs(b.y);
}
int main()
{
     
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
     
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        double k=y*1.0/x;
        if(!vis.count(k)) vis[k]=cnt++;
        E[vis[k]].push_back(node(x*x+y*y,c,y));
    }
    for(int i=0;i<cnt;i++)
    {
     
        sort(E[i].begin(),E[i].end(),cmp);
        f[i][0][0]=E[i].size();
        f[i][1][0]=E[i][0].t;
        f[i][1][1]=E[i][0].v;
        for(int j=1;j<E[i].size();j++)
        {
     
            f[i][j+1][0]=f[i][j][0]+E[i][j].t;
            f[i][j+1][1]=f[i][j][1]+E[i][j].v;
        }
    }
    for(int i=0;i<cnt;i++)
    {
     
        for(int j=m;j>=0;j--)
        {
     
            for(int k=1;k<=f[i][0][0];k++)
            {
     
                if(j>=f[i][k][0]) dp[j]=max(dp[j],dp[j-f[i][k][0]]+f[i][k][1]);
                else break;
            }
        }
    }
    printf("%d
",dp[m]);
    return 0;
}