BZOJ3628:[JLOI2014]天天酷跑 dp

思路:

绝对是逗逼题,今年四月份的时候我居然都不会做...果然是幼儿园水平无力啊...

枚举Maxh,以及Maxcombo(什么枚举?没错就是枚举)

用一个Hash表存一下状态,然后随便分层dp就过了.

具体的状态设计见代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
 
int n,m,c1,c2;
 
int w[100010][21];
int Maxh,Maxn;
int res,ansh,ansn;
 
int f[2][21][21][6];
struct State{
    int y,h,t;
    State(){}
    State(int _y,int _h,int _t):y(_y),h(_h),t(_t){}
};
struct HashSet{
    int s[21][21][6],cnt;
    State sav[21*21*6];
    inline void reset(){cnt=0,memset(s,0xc0,sizeof s);}
    inline int Max(){
        int res=-1<<30;
        for(int j=1;j<=cnt;++j)res=max(res,s[sav[j].y][sav[j].h][sav[j].t]);
        return res;
    }
    inline void insert(State x,int w){
        if(s[x.y][x.h][x.t]==0xc0c0c0c0)s[x.y][x.h][x.t]=w,sav[++cnt]=x;
        else if(w>s[x.y][x.h][x.t])s[x.y][x.h][x.t]=w;
    }
}S[2];
inline void relax(int lab,int x,int y,int h,int t,int lastw){
    if(w[x][y]==-1)return;
    S[lab].insert(State(y,h,t),lastw+w[x][y]);
}
inline void Solve(){
    int now=0,last=1,ans=0xc0c0c0c0;
    S[now].reset(),S[now].insert(State(1,0,Maxn),0);
    register int i,j;
    State p;int w;
    for(i=1;i<=n;++i){
        swap(now,last),S[now].reset();
        for(j=1;j<=S[last].cnt;++j){
            p=S[last].sav[j],w=S[last].s[p.y][p.h][p.t];
            if(p.y==1){
                relax(now,i,1,0,Maxn,w);
                relax(now,i,2,Maxh-1,Maxn-1,w);
            }
            else if(p.h==0){
                if(p.t)relax(now,i,p.y+1,Maxh-1,p.t-1,w);
                relax(now,i,p.y-1,0,p.t,w);
            }
            else relax(now,i,p.y+1,p.h-1,p.t,w);
        }
    }
    ans=max(ans,S[now].Max()-(Maxn-1)*c2-(Maxh-1)*c1);
    if(ans>res)res=ans,ansn=Maxn,ansh=Maxh;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&c1,&c2);register int i,j;
    for(j=1;j<=m;++j)for(i=1;i<=n;++i)scanf("%d",&w[i][j]);
     
    res=0xc0c0c0c0;
    for(Maxn=1;Maxn<=5;++Maxn)
        for(Maxh=1;Maxh*Maxn<m;++Maxh)
            Solve();
     
    if(res==0xc0c0c0c0)puts("mission failed");else printf("%d %d %d\n",res,ansn,ansh);
     
    return 0;
}