数据中不会出现SI = 0的情况吧。
我是先按时间从小到大排序(即按g[i].t排序)，然后方程是d[i] = max(d[j]+g[i].p);
(j<i&& fabs(g[i].s-g[j].s)<=g[i].t-g[j].t）
请问方程有错吗？
下面是我的代码，谢谢。。  o(∩_∩)o
////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 110;
struct ganster
{
    int t,p,s;
    ganster()
    {
        t = p = s = 0;
    }
};
int d[MAXN];
ganster g[MAXN];
int n,k,t;
int ans = 0;
bool cmp(ganster g1,ganster g2)
{
    if(g1.t==g2.t)
    {
        return g1.s<g2.s;
    }
    return g1.t < g2.t;
}
void dp()
{
    d[0]=0;
    ans = 0;
    //cout<<ans<<endl;
    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<i;j++)
        {
            if (((int)fabs((g[i].s-g[j].s))<=(g[i].t-g[j].t)))
            {
             //   cout<<"g[i]"<<g[i].s<<" "<<g[j].s<<endl;
                if (g[i].p+d[j]>d[i])
                {
                 //   cout<<g[i].p<<" "<<d[j]<<endl;
                    d[i] = (g[i].p + d[j]);
                }
            }
        }
        if (d[i]>ans)
        {
            //cout<<i<<endl;
            ans = d[i];
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&k,&t);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&g[i].t);
    }
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&g[i].p);
       /* if(g[i].t==0&&g[i].s!=0)
        {
            g[i].p = 0;
        }*/
    }
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&g[i].s);
       /* if(g[i].s==0)
        {
            ans += g[i].p;
        }*/
    }
    sort(g+1,g+n+1,cmp);
    g[0].s = 0;g[0].t = 0;
    dp();
    printf("%d\n",ans);
    return 0;
}
////////////////////////////////////////////////////////

• Re:WA了好多次求助 (1990) lee41sum 2009-09-04 23:12:48