1 条题解

  • 0
    @ 2022-8-16 22:11:03
    #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;
    }
    
    • 1

    信息

    ID
    237
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    4
    已通过
    3
    上传者