dp拿了满分，不会写暴搜qwq

cannotdp @ 2022-01-20 09:56:05

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int a[1005][1005];
int ans;
void dfs(int x,int y,int sum){
    if(x==n){
        ans=max(ans,sum);
        return;
    }
    dfs(x+1,y,sum+a[x+1][y]);
    dfs(x+1,y+1,sum+a[x+1][y+1]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>a[i][j];
    dfs(1,1,0);
    cout<<ans;
    return 0;
}

by shzuaeno @ 2022-01-20 09:59:36

az

by RYANGSJ @ 2022-01-20 09:59:59

。。。所以你要问什么

by cannotdp @ 2022-01-20 10:01:33

@RYANGSJ 暴搜怎么改啊qwq

by RainFestival @ 2022-01-20 10:04:26

你这个就是爆搜罢

by cannotdp @ 2022-01-20 10:05:19

@RainFestival 不知道为什么暴搜没过样例拿了11分

by abruce @ 2022-01-20 10:06:02

他的意思是说这个代码是爆搜，求改

by abruce @ 2022-01-20 10:07:32

@十年OI一场空 你的爆搜没有把金字塔尖的贡献算进去

by cannotdp @ 2022-01-20 10:09:02

@abruce 什么意思

by cannotdp @ 2022-01-20 10:09:24

@abruce 抱歉我不懂啊这

by abruce @ 2022-01-20 10:09:50

@十年OI一场空

dfs(1,1,0); 改成 dfs(1,1,a[1][1]);