ZOJ - 3450 Doraemon's Railgun （dp）

题意

一座位落（X0，Y0）的城市将遭受n个敌人的摧残。现在我们手上有某科学的超电磁炮，每次攻击都是一条射线，对于共线的敌人，必须先打倒离得近的。打倒每个敌人需花费Ti时间，并歼灭Wi个小兵。如今只剩下T0时间了！问怎么射击才可杀最多？

分析

把位于同一个射线的敌人分为一组，处于后面的敌人的时间和价值是叠加的。这样进行背包dp。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <algorithm>

#include <cmath>

#include <ctime>

#include <vector>

#include <queue>

#include <map>

#include <stack>

#include <set>

#include <bitset>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define ms(a, b) memset(a, b, sizeof(a))

#define pb push_back

#define mp make_pair

#define pii pair<int, int>

#define IOS ios::sync_with_stdio(0);cin.tie(0);

#define random(a, b) rand()*rand()%(b-a+1)+a

#define pi acos(-1.0)

const ll INF = 0x3f3f3f3f3f3f3f3fll;

const int inf = 0x3f3f3f3f;

const int maxn = 1e5+;

const int maxm = 1e5+;

const ll mod = 1e9+;

struct ND{

    ll x,y,t,w;

    ND(){}

    ND(int _x,int _y,int _t,int _w){ x=_x,y=_y,t=_t,w=_w; }

    bool operator <(const ND &a)const{

        return x*x+y*y<a.x*a.x+a.y*a.y;

    }

}p[];

bool aLine(ND a,ND b){

    if(a.x*b.y==a.y*b.x) return a.x*b.x>=&&a.y*b.y>=;

    return false;

}

vector<ND> group[];

bool vis[];

ll dp[];

int main(){

#ifdef LOCAL

    freopen("in.txt", "r", stdin);

//    freopen("output.txt", "w", stdout);

#endif

    int x0,y0,t,n;

    while(~scanf("%d%d%d%d",&x0,&y0,&n,&t)){

        for(int i=;i<n;i++){

            scanf("%lld%lld%lld%lld",&p[i].x,&p[i].y,&p[i].t,&p[i].w);

            group[i].clear();

            p[i].x-=x0;

            p[i].y-=y0;

        }

//        if(aLine(p[0],p[1])) puts("YED");

        sort(p,p+n);//按距城市的距离排序

        memset(vis,false,sizeof(vis));

        int cnt=;

        for(int i=;i<n;i++){//分组

            if(!vis[i]){

                group[cnt].push_back(p[i]);

                vis[i]=true;

                for(int j=i+;j<n;j++){

                    if(aLine(p[i],p[j])){

                        vis[j]=true;

                        if(p[j].t==){

                            group[cnt][group[cnt].size()-].w+=p[j].w;

                            continue;

                        }

                        group[cnt].push_back(p[j]);

                        group[cnt][group[cnt].size()-].w+=group[cnt][group[cnt].size()-].w;

                        group[cnt][group[cnt].size()-].t+=group[cnt][group[cnt].size()-].t;

                    }

                }

                cnt++;

            }

        }

//        for(int i=0;i<cnt;i++){

//            for(int j=0;j<group[i].size();j++){

//                cout<<'('<<group[i][j].x<<','<<group[i][j].y<<')'<<' ';

//            }cout<<endl;

//        }

        memset(dp,,sizeof(dp));

        for(int i=;i<cnt;i++){

            for(int j=t;j>=;--j){

                for(int k=;k<group[i].size()&&group[i][k].t<=j;k++){

                    dp[j]=max(dp[j],dp[j-group[i][k].t]+group[i][k].w);

                }

            }

        }

        cout<<dp[t]<<endl;

    }

    return ;

}