题目链接
典型的 DP，如果不加限制条件的话就是从上到下找一条最长路，但是限制了每行只能选 3 个，所以就多加一维，状态转移方程为： d p [ i ] [ j ] [ k ] = m a x ( d p [ i − 1 ] [ j ] [ 3 ] + g [ i ] [ j ] , m a x ( d p [ i ] [ j − 1 ] [ k − 1 ] + g [ i ] [ j ] , d p [ i ] [ j − 1 ] [ k ] ) ) dp[i][j][k]=max(dp[i-1][j][3]+g[i][j],max(dp[i][j-1][k-1]+g[i][j],dp[i][j-1][k])) dp[i][j][k]=max(dp[i−1][j][3]+g[i][j],max(dp[i][j−1][k−1]+g[i][j],dp[i][j−1][k])) AC代码如下：
#include<bits/stdc++.h> typedef long long ll; using namespace std; const int N=3e3+5; ll r,c,k,x,y,z,g[N][N],dp[N][N][4]; int main() { cin>>r>>c>>k; while(k--){ cin>>x>>y>>z; g[x][y]=z; } for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ for(int k=1;k<=3;k++){ dp[i][j][k]=max(dp[i-1][j][3]+g[i][j],max(dp[i][j-1][k-1]+g[i][j],dp[i][j-1][k])); } } } cout<<dp[r][c][3]; }