题解 P3257 【[JLOI2014]天天酷跑】

thmyl · 2017-09-06 16:06:45 · 题解

http://www.cnblogs.com/thmyl/p/7485186.html

记忆化搜索

定义状态f[i][j][o]表示处于x，y这个位置，还剩余o次连跳数的最大收益

如果是跑——f[i][j][o]=max(f[i][j+1][o]+w[i][j]) w[i][j]为这点的权值；

如果是跳的话——f[i][j][o]=max(f[i+跳跃高度（high）][j+high][o--]+hhh+w[i][j]) hhh跳跃上升过程中得到的金币数。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
#define inf 1<<30
#define maxn 100010
bool vis[25][maxn][6];
int f[25][maxn][6],map[25][maxn];
int n,m,c1,c2,ans=-inf,ans1,ans2,h,num;
int dfs(int x,int y,int now){
    if(x>n)return 0;
    if(map[y][x]==-1)return -inf;
    if(vis[y][x][now])return f[y][x][now];
    int tot=-inf,sum=0;bool flag=1;
    if(y==1)now=0;
    if(now<num){
        for(int i=1;i<h;i++){
            if(map[y+i][x+i]==-1){flag=0;break;}
            sum+=map[y+i][x+i];
        }
        if(flag)tot=max(tot,sum+dfs(x+h,y+h,now+1));
    }
    if(y==1)tot=max(tot,dfs(x+1,y,0));
    if(y>1)tot=max(tot,dfs(x+1,y-1,now));
    vis[y][x][now]=1;
    f[y][x][now]=tot+map[y][x];
    return f[y][x][now];
}
int main(){
    scanf("%d%d%d%d",&n,&m,&c1,&c2);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&map[i][j]);
    for(num=1;num<=5;num++){
        for(h=1;h*num<m;h++){
            memset(f,-1,sizeof(f));
            memset(vis,0,sizeof(vis));
            int tot=dfs(0,1,m)-c2*(num-1)-c1*(h-1);
            if(ans<tot)ans=tot,ans1=num,ans2=h;
        }
    }
    if(ans>0)printf("%d %d %d",ans,ans1,ans2);
    else printf("mission failed");
    return 0;
}