2010-1145

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意，攻打来袭的敌人，攻打第i组敌人耗时ti，可以消灭敌人wi，求在T时间内最多可以消灭的敌人数，但有一个限制条件：告诉了每组敌人坐标和自己的坐标，对于位于一条线上的所有组敌人，每次攻打只能攻打离自己最近的那组。[[BR]]
背包问题，对于在一条线上的敌人，可以看做是一个物品处理，例如1,2,3这三组是在一条线上的敌人组，那把他们看做一个物品，要么攻打1，要么攻打1+2，要么攻打1+2+3，只能是选择一种这其中一种方案。[[BR]]
寻找位于一条线上敌人组的方法，我是利用斜率排序的（感觉此方法不佳），也可以用gcd来寻找。
{{{
#!cpp
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAX 10000000.00
using namespace std;
struct node
{
    long x,y,t,w;
    double k;
};
bool cmp(node x,node y) { return (x.k<y.k );}
bool cmp1(node x,node y){ if (x.x==y.x) return (x.y<y.y); else return (x.x<y.x ); }
int main()
{
    long x0,y0,n,t0,j,k,i,midq,midh,i1,j1,k1,time,ren;
    node a[600];
    long f[10100];
    while(scanf("%ld%ld%ld%ld",&x0,&y0,&n,&t0)!=EOF)
    {
        for (j=1;j<=n;++j)
        {
            scanf("%ld%ld%ld%ld",&k,&i,&a[j].t,&a[j].w);
            a[j].x=k-x0;
            a[j].y=i-y0;
            if (k==x0) a[j].k=MAX; else a[j].k=1.00*(i-y0)/(k-x0);
        }
        sort(a+1,a+1+n,cmp);

        i=1;j=1;
        while(j<=n)
        {
            while(i<=n&&fabs(a[i].k-a[j].k)<0.00001) ++i;
            sort(a+j,a+i,cmp1);
            j=i;
        }
        memset(f,0,sizeof(f));
        j=1;i=1;

        while(j<=n)
        {
            while(i<=n && fabs(a[i].k-a[j].k)<0.00001) ++i;
            midq=i-1;
            midh=j;
            if (a[j].k==MAX)
            {
                while(midq>=midh && a[midq].y>0) --midq;
                midh=midq; midq++;
            }
            else
            {
                while(midq>=midh && a[midq].x>0) --midq;
                midh=midq; midq++;
            }

            for (j1=t0;j1>=0;--j1)
            {
                time=0; ren=0;
                for (i1=midq;i1<=i-1;++i1) 
                {
                    time+=a[i1].t; ren+=a[i1].w;
                    if (j1-time>=0&& f[j1-time]+ren>f[j1] ) f[j1]=f[j1-time]+ren;
                }
            }

            for (j1=t0;j1>=0;--j1)
            {
                time=0; ren=0;
                for (i1=midh;i1>=j;--i1) 
                {
                    time+=a[i1].t; ren+=a[i1].w;
                    if (j1-time>=0&& f[j1-time]+ren>f[j1] ) f[j1]=f[j1-time]+ren;
                }
            }

            j=i;
        }
        printf("%ld\n",f[t0]);
    }
    return 0;
}
}}}

题目大意，攻打来袭的敌人，攻打第i组敌人耗时ti，可以消灭敌人wi，求在T时间内最多可以消灭的敌人数，但有一个限制条件：告诉了每组敌人坐标和自己的坐标，对于位于一条线上的所有组敌人，每次攻打只能攻打离自己最近的那组。

背包问题，对于在一条线上的敌人，可以看做是一个物品处理，例如1,2,3这三组是在一条线上的敌人组，那把他们看做一个物品，要么攻打1，要么攻打1+2，要么攻打1+2+3，只能是选择一种这其中一种方案。

寻找位于一条线上敌人组的方法，我是利用斜率排序的（感觉此方法不佳），也可以用gcd来寻找。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAX 10000000.00
using namespace std;
struct node
{
    long x,y,t,w;
    double k;
};
bool cmp(node x,node y) { return (x.k<y.k );}
bool cmp1(node x,node y){ if (x.x==y.x) return (x.y<y.y); else return (x.x<y.x ); }
int main()
{
    long x0,y0,n,t0,j,k,i,midq,midh,i1,j1,k1,time,ren;
    node a[600];
    long f[10100];
    while(scanf("%ld%ld%ld%ld",&x0,&y0,&n,&t0)!=EOF)
    {
        for (j=1;j<=n;++j)
        {
            scanf("%ld%ld%ld%ld",&k,&i,&a[j].t,&a[j].w);
            a[j].x=k-x0;
            a[j].y=i-y0;
            if (k==x0) a[j].k=MAX; else a[j].k=1.00*(i-y0)/(k-x0);
        }
        sort(a+1,a+1+n,cmp);
        i=1;j=1;
        while(j<=n)
        {
            while(i<=n&&fabs(a[i].k-a[j].k)<0.00001) ++i;
            sort(a+j,a+i,cmp1);
            j=i;
        }
        memset(f,0,sizeof(f));
        j=1;i=1;
        while(j<=n)
        {
            while(i<=n && fabs(a[i].k-a[j].k)<0.00001) ++i;
            midq=i-1;
            midh=j;
            if (a[j].k==MAX)
            {
                while(midq>=midh && a[midq].y>0) --midq;
                midh=midq; midq++;
            }
            else
            {
                while(midq>=midh && a[midq].x>0) --midq;
                midh=midq; midq++;
            }
            for (j1=t0;j1>=0;--j1)
            {
                time=0; ren=0;
                for (i1=midq;i1<=i-1;++i1) 
                {
                    time+=a[i1].t; ren+=a[i1].w;
                    if (j1-time>=0&& f[j1-time]+ren>f[j1] ) f[j1]=f[j1-time]+ren;
                }
            }
            for (j1=t0;j1>=0;--j1)
            {
                time=0; ren=0;
                for (i1=midh;i1>=j;--i1) 
                {
                    time+=a[i1].t; ren+=a[i1].w;
                    if (j1-time>=0&& f[j1-time]+ren>f[j1] ) f[j1]=f[j1-time]+ren;
                }
            }
            j=i;
        }
        printf("%ld\n",f[t0]);
    }
    return 0;
}