icpc:problems:luogup1796
problems | |
---|---|
名称 | 汤姆斯的天堂梦 |
题目编号 | P1796 |
题目链接 | luogu.com.cn/… |
来源 | Luogu |
算法分类 | 动态规划, 线性动态规划 |
难易程度 | 容易 |
汤姆斯的天堂梦
想法
读入时进行转移,使用f[i][j]
记录第i
层第j
个的最优值。
代码实现
#include<cstdio> const int N = 110; int f[N][N], line[N], maps[N][N]; int main() { int n; scanf("%d", &n); for(int i=1; i<=n; i++) { int target, val; scanf("%d", &line[i]); for(int j=1; j<=line[i]; j++) { f[i][j] = 0x7f7f7f7f; while(true) { scanf("%d", &target); if(target == 0)break; scanf("%d", &val); if(f[i-1][target] + val < f[i][j]) f[i][j] = f[i-1][target] + val; } } } int mx = f[n][1]; for(int i=1; i<=line[n]; i++) if(mx > f[n][i]) mx = f[n][i]; printf("%d", mx); return 0; }
/app/www/public/data/pages/icpc/problems/luogup1796.txt · 最后更改: 2024/03/21 08:48 由 温婕莺