题解 [ABC344F] Earn to Advance
cjh20090318
·
·
题解
感觉不难，但是没能场切。
题意
题目翻译非常清晰。
分析
观察到最优路径上停留获取金币点的 P 一定是单调递增的，正确性显然。
简单证明一下，设停留获取金币点的序列为 p，如果存在 i<j,P_{p_i}>P_{p_j}，那么就可以在 p_i 的位置上花比 p_j 更少的步数来获取在 p_j 上获得同样多的钱。
设 h_{i,j} 表示从 (1,1) 走到 (i,j) 所需的最小步数，q_{i,j} 表示从 (1,1) 走到 (i,j) 步数的最小情况下剩余最多前的数量，g_{i,j,k,l} 表示从 (k,l) 到 (i,j) 需要最少钱的数量（需要保证 k \le i,l \le j）。
$$
h_{i,j} = \min\limits_{k \le i,l \le j}
\left( h_{k,l} + \left\lceil\dfrac{\max(g_{i,j,k,l}-q_{k,l},0)}{P_{k,l}}\right\rceil + i-k + j-l \right)
$$
最终的答案就是 $h_{n,n}$。
## 代码
```cpp
//the code is from chenjh
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int n;
int p[88][88],r[88][88],d[88][88];//分别对应题目中的 P,R,D。
LL g[88][88][88][88],h[88][88],q[88][88];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) scanf("%d",&p[i][j]);
for(int i=1;i<=n;i++)for(int j=1;j<n;j++) scanf("%d",&r[i][j]);
for(int i=1;i<n;i++)for(int j=1;j<=n;j++) scanf("%d",&d[i][j]);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
memset(g[i][j],0x3f,sizeof(g[i][j]));
g[i][j][i][j]=0;//从 (i,j) 往 (k,l) 逆序递推。
for(int k=i;k>0;--k)for(int l=j-(k==i);l>0;--l)
g[i][j][k][l]=min(g[i][j][k+1][l]+d[k][l],g[i][j][k][l+1]+r[k][l]);//从下方和右方转移。
}
memset(h,0x3f,sizeof h);
h[1][1]=r[1][1]=0;
for(int i=1;i<=n;i++)for(int j=1+(i==1);j<=n;j++){
for(int k=1;k<=i;k++)for(int l=1;l<=j;l++){//枚举最后停留获取钱的位置。
LL t=max((g[i][j][k][l]-q[k][l]+p[k][l]-1)/p[k][l],0ll);//需要停留的步数，向上取整使用鸽巢原理转为向下取整。
if(h[k][l]+t+i-k+j-l<h[i][j])
h[i][j]=h[k][l]+t+i-k+j-l,//更新最短步数。
q[i][j]=t*p[k][l]+q[k][l]-g[i][j][k][l];//更新剩余的钱。
else if(h[i][j]==h[k][l]+t+i-k+j-l && t*p[k][l]+q[k][l]-g[i][j][k][l]>q[i][j])//步数相等就求钱剩的最多。
q[i][j]=t*p[k][l]+q[k][l]-g[i][j][k][l];
}
}
printf("%lld\n",h[n][n]);
return 0;
}
```