xfstart07
Get busy living or get busy dying

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;

constintINF=-0x7FFFFFFF;
intW,H,P,N,T;
intAns1,Ans2;
intA[2100][550];
intF[2100][550];
intmain()
{
    scanf("%d%d%d%d",&W,&P,&H,&N);
    memset(A,0,sizeof(A)); Ans2=T=0;
    for(inti=1;i<=N;++i){
        intt,w,v,s;
        scanf("%d%d%d%d",&t,&w,&v,&s);
        if(H%v!=0){Ans2+=s; continue; }
        if(t+H/v>T) T=t+H/v;
        if(t+H/v<abs(P-w)){Ans2+=s; continue; }
        A[t+H/v][w]+=s;
    }
    for(inti=0;i<=T;++i)
        for(intj=1;j<=W;++j)
            F[i][j]=INF;
    Ans1=F[0][P]=A[0][P];
    for(inti=1;i<=T;++i)
        for(intj=1;j<=W;++j){
            for(intk=-1;k<=1;++k)
                if(j-k>0&&j-k<=W&&F[i-1][j-k]>F[i][j])
                    F[i][j]=F[i-1][j-k];
            F[i][j]+=A[i][j];
        }
    for(inti=1;i<=W;++i)
        if(F[T][i]>Ans1) Ans1=F[T][i];
    printf("%d\n%d\n",Ans1,Ans2);
    return0;
}






posted on 2009-08-12 20:11 xfstart07 阅读(147) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理