题解：P13501 「Cfz Round 6」Imaichi
dream_on_screen · · 题解
::::info[真的有人会关心题目名称吗？]
题目背景是日语歌词，所以猜测题目名称是日语单词，尝试用平假名拼写，得到了いまいち。
いまいち (imaichi)
词性： 副词 / 形容动词词干 (口语化、较随意)
含义： 来源于“今一つ (いまひとつ)”，意思是“还差一点”、“不够好”、“不太满意”、“差强人意”。形容感觉上稍有欠缺，未能达到理想状态。
摘自 DeepSeek。
虽然我不能得知这题目名称背后的含义，其中的含义又岂可与人语，大概只有经历过才能知道吧。但是如果这篇题解有幸能被 Cfz 看到，能否告诉我我的猜测是否正确？
::::
虽然我没能通过这道题，但是我认为我的做法时间复杂度是正确的，仍然具有参考价值。
赛后我在 DeepSeek 的帮助下获得了 AC，但是写出了 7.33KB 史山，反而不具有参考价值。以下题解只介绍原来的做法，由于常数过大与水平有限卡常失败，即使时间复杂度是正确的也会 TLE 70pts，但我认为这样的思路仍然具有参考价值。
题目描述
Yuki 需要在
思路
每一步只能向左边、右边、或者下边走。所以可以在一行里反复移动。
如果
所以说当我们走到某个格子的时候，不必着急向下走，可以到这一行的刷钱点把摩拉刷到上限。但是即使在刷钱点刷到
我们称在
记
可以发现，
所以，设
但是，我们还可以在某个地方得到在这个地方可以获得的最多的摩拉之后不再返回原点，而是走向其他地方。显然当在一个地方获得最多的摩拉之后向一个方向移动一定不劣。所以可以从左往右递推然后从右往左递推。具体来说，在从左往右递推时可以记录走到某一点时剩余最大的摩拉数量，如果现在最大的摩拉数量超过原来的就更新最大数量。从右往左同理。
但是，需要考虑并不是每一个
总时间复杂度为
最后是乱七八糟的代码。但是因为常数太大水平有限不会卡常 TLE 70pts，但是就算不够完美也好。
#include <bits/stdc++.h>
//...
//真的对吗?
using namespace std;
int n,m,s,k;
int a[1023][1023];
int e[1023][1023],dp[1023][1023];//进入时在结算后最多还剩多少钱，将要退出时最多还剩多少钱
constexpr int inf=0x3f3f3f3f;
int p[1023],q[1023];//去的时候至少要多少钱和回来的时候最多还剩多少钱
//p是说在结算这个格子之前至少要有多少钱
bool flag1[1023],flag2[1023],flag[1023];//从可以开始的点出发，有哪些点是可以到达的
int mian()
{
cin>>n>>m>>s>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
e[i][j]=dp[i][j]=-inf;
for(int i=0;i<=m+1;i++)
p[i]=inf,q[i]=-inf;
p[0]=0,p[m+1]=0;
for(int i=1;i<=m;i++)
{
int p=k<s+a[1][i]?k:s+a[1][i];
if(p>=0)
e[1][i]=p;
}
for(int i=1;i<n;i++)
{
for(int j=1;j<=m;j++)
dp[i][j]=e[i][j];
memset(flag1,0,sizeof(flag1));
memset(flag2,0,sizeof(flag2));
for(int j=m;j>=1;j--)
{
if(e[i][j]>=0)
{
int cur=j,remain=e[i][j];
while(cur<=n&&remain>=0)
{
flag1[cur]=true;
if(cur!=j)
remain=min(remain+a[i][cur],k);
cur++;
}
}
}
for(int j=1;j<=m;j++)
{
if(e[i][j]>=0)
{
int cur=j,remain=e[i][j];
while(cur>=1&&remain>=0)
{
flag2[cur]=true;
if(cur!=j)
remain=min(remain+a[i][cur],k);
cur--;
}
}
}
for(int j=1;j<=m;j++)
flag[j]=flag1[j]|flag2[j];
//考虑向左走找到刷钱点
int last=-inf;
for(int j=1;j<=m;j++)
p[j]=inf,q[j]=-inf;
for(int j=1;j<=m;j++)
{
//判断这是不是刷钱点
//刷钱点是两个正数或者一正另一个<=0，应该算从最近的正数出发或者到最近的正数
//我们认为刷钱点在j，当且仅当a_{j-1}与a_j构成了一个刷钱点，且a_j>0
//其实a_j在左边也可以
//而且还要可以走到
if(flag[j]&&((j!=1&&a[i][j-1]+a[i][j]>0&&a[i][j]>=0)||(j!=m&&a[i][j]+a[i][j+1]>0&&a[i][j]>=0)))
{
//发现刷钱点
p[j]=0,q[j]=k;
last=j;
continue;
}
if(last==-inf)
continue;
//我们需要维护从上一个刷钱点到j还剩多少钱
//还有从j走入上一个刷钱点在开始时至少要多少钱
//第一点显然
q[j]=min(q[j-1]+a[i][j],k);
if(q[j]<0)//无法抵达j
q[j]=-inf;
p[j]=max(p[j-1]-a[i][j],0);
if(p[j]>k)
p[j]=inf;
}
for(int j=1;j<=m;j++)
if(p[j-1]<=e[i][j])
dp[i][j]=max(dp[i][j],q[j]);
//向右走到刷钱点同理
last=inf;
for(int j=1;j<=m;j++)
p[j]=inf,q[j]=-inf;
for(int j=m;j>=1;j--)
{
if(flag[j]&&((j!=m&&a[i][j+1]+a[i][j]>0&&a[i][j]>=0)||(j!=1&&a[i][j]+a[i][j-1]>0&&a[i][j]>=0)))
{
p[j]=0,q[j]=k;
last=j;
continue;
}
if(last==inf)
continue;
q[j]=min(q[j+1]+a[i][j],k);
if(q[j]<0)
q[j]=-inf;
p[j]=max(p[j+1]-a[i][j],0);
if(p[j]>k)
p[j]=k;
}
for(int j=1;j<=m;j++)
if(p[j+1]<=e[i][j])
dp[i][j]=max(dp[i][j],q[j]);
//但是我们可以从一个格子走到其他地方，需要考虑走到其他地方还剩多少
//对于每两个刷钱点之间的格子，一定从刷钱点出发最优
int remain=-inf;
for(int j=1;j<=m;j++)//往右走
{
if((remain>=0||flag[j])&&((j!=1&&a[i][j-1]+a[i][j]>0&&a[i][j]>=0)||(j!=m&&a[i][j]+a[i][j+1]>0&&a[i][j]>=0)))
{
remain=k;
dp[i][j]=max(dp[i][j],remain);
continue;
}
remain=min(remain+a[i][j],k);
remain=max(dp[i][j],remain);
if(remain<0)
remain=-inf;
dp[i][j]=max(dp[i][j],remain);
}
remain=-inf;
for(int j=m;j>=1;j--)//往右走
{
if((remain>=0||flag[j])&&((j!=1&&a[i][j-1]+a[i][j]>0&&a[i][j]>=0)||(j!=m&&a[i][j]+a[i][j+1]>0&&a[i][j]>=0)))
{
remain=k;
dp[i][j]=max(dp[i][j],remain);
continue;
}
remain=min(remain+a[i][j],k);
remain=max(dp[i][j],remain);
if(remain<0)
remain=-inf;
dp[i][j]=max(dp[i][j],remain);
}
for(int j=1;j<=m;j++)
{
int next=min(k,dp[i][j]+a[i+1][j]);
if(next>=0)
e[i+1][j]=next;
}
}
int ans=-inf;
for(int i=1;i<=m;i++)
if(e[n][i]>ans)
ans=e[n][i];
if(ans==-inf)
cout<<"-1\n";
else
cout<<ans<<"\n";
return 0;//完结撒花
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int ID,t;
cin>>ID>>t;
for(int i=1;i<=t;i++)
mian();
return 0;
}