洛谷 1359. 租用游艇
原题链接
简单
作者:
我是java同学
,
2023-02-14 18:35:22
,
所有人可见
,
阅读 124
dp
- 集合:
f[i]
:走到第i个出租站所需要的费用
- 状态计算
- 选
i
:f[i]
(从1
到i
的费用)
- 不选
i
: f[i - 1] + a[i][j]
- 循环方式可以用求最长上升子序列的方式
- 注意半矩形的输入方式
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1000010, M = 210;
int n;
int w[M][M];
int f[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i < n; i ++ )
for (int j = i + 1; j <= n; j ++ )
cin >> w[i][j];
for (int i = 1; i <= n; i ++ )
{
f[i] = w[1][i];
for (int j = 1; j < i; j ++ )
f[i] = min(f[i], f[j] + w[j][i]);
}
cout << f[n] << endl;
return 0;
}
java同学怎么写的全是c++呀
java代码长执行时间也长,java同学也嫌弃