1 条题解
-
0
#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
- 上传者