题解

这题有点像dp中的DJ

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

long long dp[305][605],a[305][605];

int main(){
    memset(dp,0x3c,sizeof dp);
    dp[1][1] = 0;
    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= i * 2 - 1;j ++){
            cin >> a[i][j];
            dp[i][j] += a[i][j];
            dp[i + 1][j] = min(dp[i + 1][j],dp[i][j]);
            dp[i + 1][j + 1] = min(dp[i + 1][j + 1],dp[i][j]);
            dp[i + 1][j + 2] = min(dp[i + 1][j + 2],dp[i][j]);
        }
    }
    long long ans = 1e9;
    for(int i = 1;i <= n * 2 - 1;i ++){
        ans = min(ans,dp[n][i]);
    }
    cout << ans;
    return 0;
}