p1297

stm来源noi,吓死了.

之前多次路过这道题,发现处理每个馅饼的到达时间好像可以是向下取整也可以是向上取整,如果对着样例调的话又很浪费时间,于是一直没写.况且学姐说数据错了.今天突然发现是刚好到达才算,那就好搞很多.

考虑每个馅饼到达底部的时间应该是tt+(h-1)/tv,然后对于时间和位置做二维dp就好了.由于一定需要刚好到达,所以需要h--后h%tv==0才能用来更新.

然后二维dp也不难推,码代码的时候多尝试几次就好了.

(这道题不会用read(),因为没有规定个数,read()又没有返回能否读入的东西,反正数量应该不多就直接cin了)

using namespace std;

int next;
int ans[1200][110];
int h,w,m;
int i,f,k;
int tt,tx,tv,tw,t;
inline int maxx()
{
    m=0;
    if(f-2>0&&ans[i+1][f-2]>m) m=ans[i+1][f-2],next=-2;
    if(f-1>0&&ans[i+1][f-1]>m) m=ans[i+1][f-1],next=-1;
    if(ans[i+1][f]>m)          m=ans[i+1][f],next=0;
    if(ans[i+1][f+1]>m)        m=ans[i+1][f+1],next=1;
    if(ans[i+1][f+2]>m)        m=ans[i+1][f+2],next=2;
    return m;
}
int main() 
{ 
    cin>>w>>h;
    h--;
    while(cin>>tt>>tx>>tv>>tw)
    {
        if(h%tv)continue;
        tt+=h/tv;
        ans[tt][tx]+=tw;
        t=max(t,tt);
    }
    for(i=t-1;i>=0;i--)
        for(f=w;f;f--)
            ans[i][f]+=maxx();
    write(ans[0][w/2+1]);
    
    for(i=0,f=w/2+1;;i++)
    {
        if(!maxx())break;
        f+=next;
        write(next);
    }
    return 0;
}

(悄悄百度了一下发现是noi导刊的题,难度就还好吧.