如果a里面有$0$,那么```dp[l][r]```就会有$0$,那么某些特殊情况下```dfs```中的```if(dp[l][r])```就会一直不满足条件,不停```dfs```递归下去,最后就```dp[l][r]=max(dfs(l,r-1,n)+a[r]*quick_pow(2,(n-r+l)),dfs(l+1,r,n)+a[l]*quick_pow(2,(n-r+l)));```这一行会访问到```a[-1]```或```a[100]```造成数组访问越界,所以$\textcolor{purple}{RE}$。
该法也很简单,在```dfs```开头加上
```cpp
if(l>r)return 0;
```
既如果区间已经不存在了,就返回$0$结束。
[AC](https://www.luogu.com.cn/record/121283717)代码:
```cpp
#include<bits/stdc++.h>
#define x first
#define y second
#define lson node<<1
#define rson node<<1|1
using namespace std;
typedef long long ll;
const int maxn=5e5+34;
__int128 a[100];//,b[maxn],vis[maxn],idx,tot;
__int128 dp[100][100];
__int128 read(){
__int128 res=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch)){
res=res*10+ch-'0';
ch=getchar();
}
return res;
}
void write(__int128 x){
if(x>9)write(x/10);
putchar(x%10+'0');
}
__int128 quick_pow(__int128 x,ll y){
__int128 res=1;
x=2;
while(y){
if(y&1)res=res*x;
x=x*x;
y>>=1;
}
return res;
}
__int128 dfs(int l,int r,int n){
if(l>r)return 0;
if(dp[l][r])return dp[l][r];
dp[l][r]=max(dfs(l,r-1,n)+a[r]*quick_pow(2,(n-r+l)),dfs(l+1,r,n)+a[l]*quick_pow(2,(n-r+l)));
//dfs(l,r-1,n)+a[r]*quick_pow(2,(n-r+l));
//dfs(l+1,r,n)+a[l]*quick_pow(2,(n-r+l));
return dp[l][r];
// return 1;
}
void work(){
int n,m,u,v,w;
scanf("%d%d",&m,&n);
__int128 ans=0;
while(m--){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)dp[i][j]=0;
}
for(int i=1;i<=n;i++)a[i]=read(),dp[i][i]=a[i]*quick_pow(2,n);
// for(int i=1;i<=n;i++)write(dp[i][i]);putchar(' ');
ans+=dfs(1,n,n);
}
write(ans);
putchar('\n');
}
int main()
{
int t=1;
// scanf("%d",&t);
while(t--)
work();
return 0;
}
```
以后遇到过样例,提交$\textcolor{purple}{RE}$,或者样例$\textcolor{purple}{RE}$,就可以尝试着下载不通过的测试点或者调试样例,试着按程序运行顺序,注释一半的代码,然后再运行看是否RE,如果RE了,说明问题出在那一半没注释的代码,否则问题出在注释了哪一半代码;然后逐渐缩小,以此类推,最后确定问题。
by wanglexi @ 2023-08-16 20:54:01
哎呀,打错一个词
```该法也很简单,在dfs开头加上```
是“改法”
by wanglexi @ 2023-08-16 20:55:35