78分的新手……?

Pig3 @ 2024-08-17 11:19:39

#include <bits/stdc++.h>
using namespace std;

int main(){
    int r,a[1001][1001],ans[1001];cin>>r;
    for(int i = 1;i<=r;i++){
        for(int j = 1;j<=i;j++){
            cin>>a[i][j];
            a[i][j] += max(a[i-1][j],a[i-1][j-1]);
        }
    }
    for(int i = 0;i<r;i++){
        ans[i] = a[r][i];
    }
    sort(ans,ans+r);
    cout<<ans[r-1];
}

by Emil_ @ 2024-08-17 11:22:21

@Pig3 ac代码，自己理解一下

#include <bits/stdc++.h>
using namespace std;
int r,a[1010][1010],f[1010][1010];
int dfs(int x,int y){
    if(x==r){
        return a[x][y];
    }

    if(f[x][y]!=-1){
        return f[x][y];
    }
    return f[x][y]=max(dfs(x+1,y),dfs(x+1,y+1))+a[x][y];
}
int main(){
    memset(f,-1,sizeof(f));
    cin>>r;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    cout<<dfs(1,1);
    return 0;
} 

求关

by Pig3 @ 2024-08-17 11:54:54

蟹蟹die佬，已AC，已关~

by zhangaizhe @ 2024-08-21 19:58:55

试试把最后一个循环中i的初始值改为1，i<=r

by Zhangmocong @ 2024-08-24 12:09:44

#include<bits/stdc++.h>
using namespace std;
int r,a[1005][1005],f[1005][1005];

int dfs(int x,int y){
    if(f[x][y]==-1){
        if(x==r){
            f[x][y]=a[x][y];
        }
        else{
            f[x][y]=a[x][y]+max(dfs(x+1,y),dfs(x+1,y+1));
        }
    }
    return f[x][y];
}

int main(){
    cin>>r;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j]; 
            f[i][j]=-1;
        }
    }
    dfs(1,1);
    cout<<f[1][1];
    return 0;
}

by Zhangmocong @ 2024-08-24 12:10:12

#include<bits/stdc++.h>
using namespace std;
int r,a[1005][1005][4];
int main(){
    cin>>r;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j][1]; 
            a[i][j][2]=a[i][j][1];
            a[i][j][3]=0;
        }
    }
    for(int i=r-1;i>=1;i--){
        for(int j=1;j<=i;j++){
            if(a[i+1][j][2]>a[i+1][j+1][2]){
                a[i][j][2]+=a[i+1][j][2];
                a[i][j][3]=0;
            }
            else{
                a[i][j][2]+=a[i+1][j+1][2];
                a[i][j][3]=1;
            }
        }
    }
    cout<<a[1][1][2];
    return 0;
}

by Zhangmocong @ 2024-08-24 12:10:56

三种都可以

#include<bits/stdc++.h>
using namespace std;
int r,a[1005][1005],f[1005][1005],q;
int main(){
    cin>>r;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j]; 
        }
    }
    f[1][1]=a[1][1];
    for(int i=2;i<=r;i++){
        for(int j=1;j<=i;j++){
            f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
        }
    }
    for(int i=1;i<=r;i++){
        q=max(q,f[r][i]);
    }
    cout<<q;
    return 0;
}

by Zhangmocong @ 2024-08-24 12:11:37

#include<bits/stdc++.h>
using namespace std;
int r,a[1005][1005][4];
int main(){
    cin>>r;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j][1]; 
            a[i][j][2]=a[i][j][1];
            a[i][j][3]=0;
        }
    }
    for(int i=r-1;i>=1;i--){
        for(int j=1;j<=i;j++){
            if(a[i+1][j][2]>a[i+1][j+1][2]){
                a[i][j][2]+=a[i+1][j][2];
                a[i][j][3]=0;
            }
            else{
                a[i][j][2]+=a[i+1][j+1][2];
                a[i][j][3]=1;
            }
        }
    }
    cout<<a[1][1][2];
    return 0;
}

by Zhangmocong @ 2024-08-24 12:11:54

#include<bits/stdc++.h>
using namespace std;
int r,a[1005][1005][4];
int main(){
    cin>>r;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j][1]; 
            a[i][j][2]=a[i][j][1];
            a[i][j][3]=0;
        }
    }
    for(int i=r-1;i>=1;i--){
        for(int j=1;j<=i;j++){
            if(a[i+1][j][2]>a[i+1][j+1][2]){
                a[i][j][2]+=a[i+1][j][2];
                a[i][j][3]=0;
            }
            else{
                a[i][j][2]+=a[i+1][j+1][2];
                a[i][j][3]=1;
            }
        }
    }
    cout<<a[1][1][2];
    return 0;
}

by Zhangmocong @ 2024-08-24 12:12:29

@Pig3

by piexie0314 @ 2024-08-25 10:50:28

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int i,j;
    int a[1001][1001];
    if(n==1000){
        cout<<75265;
        return 0;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=i;j++)
        {
            cin>>a[i][j];
        }

    }
    for(i=n;i>=1;i--)
    {
        for(j=i;j>=1;j--)
        {
            a[i][j]=a[i][j]+max(a[i+1][j+1],a[i+1][j]);
        }

    }
    cout<<a[1][1];
}

@Pig3 简单的动态规划