重点第一次想到这么简洁的dp代码，忍不住发一条
题目大意我就不描述了
这题我最开始以为的状态转移方程是 dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]+arr[i][j]) 嗯 只有8分, 后面再仔细看了一下题目意思,发现说的是i->j之间的游艇费用,而它经过j可以选择换游艇,也可以选择不换游艇继续开, 所以我们可以定义dp数组的含义为 dp[i] 表示 到达第i个游艇租用站 最少使用的费用 则到达j的最少费用为 min(dp[i] + arr[i][j]) i表示前面的站点
#include <iostream>
#define INF 100000000
using namespace std;
int n, m;
int arr[ 205 ][ 205 ];
int dp[ 205 ];
int main() {
cin >> n;
for ( int i = 1; i < n; i++ ) {
for ( int j = i + 1; j <= n; j++ ) {
cin >> arr[ i ][ j ];
}
}
dp[ 2 ] = arr[ 1 ][ 2 ];
for ( int j = 3; j <= n; j++ ) {
int minx = INF;
for ( int i = 1; i < j; i++ ) {
minx = min( minx, arr[ i ][ j ] + dp[ i ] );
}
dp[ j ] = minx;
}
// for ( int i = 1; i < n; i++ ) {
// for ( int j = i + 1; j <= n; j++ ) {
// cout << dp[ i ][ j ] << " ";
// }
// cout << endl;
// }
cout << dp[ n ];
}
// 5 2 5 7 6 3 5 9 2 8 5