题解 | 三角形取数(Hard Version)

/*#include <bits/stdc++.h>
using namespace std;
long long int a[305][605]={0};
bool isa[305][605]={0};
long long int dp[305][305][305]={0};
int main(){
    /*int s=1,t=i;
    int nowx=i,nowy=t+r-l;
    dp[i][l][r]=max(
        dp[i-1][l][r]+a[nowx-1][nowy],
        dp[i-1][l-1][r]+a[nowx-1][nowy+1],
        dp[i-1][l][r-1]+a[nowx-1][nowy-1]
    )*//*
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++){
        for(int j=n-i+1;j<=n+i-1;j++){
            cin>>a[i][j];
            isa[i][j]=1;
        }
    }
    int s=1,t=n;
    dp[s][0][0]=a[s][t];
    for(int i=2;i<=n;i++){
        for(int l=0;l<=i-1;l++){
            for(int r=0;r<=i-1;r++){
                int nowx=i,nowy=t+r-l;
                if(isa[nowx][nowy]&&l+r<=i-1){
                    dp[i][l][r]=-1e18;
                    int prex=i-1,prey=t+r-l;
                    //1正下
                    prey=t+r-l;
                    if(isa[prex][prey]){
                        dp[i][l][r]=max(
                            dp[i-1][l][r]+a[nowx][nowy],
                            dp[i][l][r]
                        );
                    }
                    //2左下
                    prey=t+r-l+1;
                    if(isa[prex][prey]){
                        dp[i][l][r]=max(
                            dp[i-1][l-1][r]+a[nowx][nowy],
                            dp[i][l][r]
                        );
                    }
                    //3右下
                    prey=t+r-1-l;
                    if(isa[prex][prey]){
                        dp[i][l][r]=max(
                            dp[i-1][l][r-1]+a[nowx][nowy],
                            dp[i][l][r]
                        );
                    }
                }
            }
        }
    }
    long long int ans=-1e18;
    for(int l=0;l<=n-1;l++){
        for(int r=0;r<=n-1;r++){
            int nowx=n,nowy=t+r-l;
            if(abs(l-r)<=k&&l+r<=n-1&&isa[nowx][nowy]){
                ans=max(ans,dp[n][l][r]);
                //cout<<"l:"<<l<<" r:"<<r<<"dp:"<<dp[n][l][r]<<'\n';
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}*/
#include <bits/stdc++.h>
using namespace std;
long long int a[305][605]={0};
bool isa[305][605]={0};
long long int dp[305][605]={0};
int main(){
    /*
    j=n+|r-l|
    n-max(k,n-1)<=j<=n+min(k,n-1);
    */
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++){
        for(int j=n-i+1;j<=n+i-1;j++){
            cin>>a[i][j];
            isa[i][j]=1;
        }
    }
    dp[1][n]=a[1][n];
    for(int i=2;i<=n;i++){
         for(int j=n-i+1;j<=n+i-1;j++){
            dp[i][j]=-1e18;
            int prex=i-1,prey=j;
            //1
            prey=j;
            if(isa[prex][prey]){
                dp[i][j]=max(dp[i][j],dp[prex][prey]+a[i][j]);
            }
            //2
            prey=j+1;
            if(isa[prex][prey]){
                dp[i][j]=max(dp[i][j],dp[prex][prey]+a[i][j]);
            }
            //3
            prey=j-1;
            if(isa[prex][prey]){
                dp[i][j]=max(dp[i][j],dp[prex][prey]+a[i][j]);
            }
        }
    }
    long long int ans=-1e18-1;
    for(int pos=n-min(k,n-1);pos<=n+min(k,n-1);pos++){
        ans=max(ans,dp[n][pos]);
    }
    cout<<ans<<'\n';
    return 0;
}