2026 ICPC Nanchang Invitational and Jiangxi Provincial Collegiate Programming Contest I题（dp)

题目链接Problem - I - Codeforceshttps://codeforces.com/gym/106551/problem/I题目大意你有4个蛋它们叠成一个塔从下到上分别叫A、B、C、DD在最顶上。这个塔站在一条长度为 l 的轨道上轨道从坐标 0 到坐标 l分成 l 段每段有不同的地形。每走一段从 x 到 x1要花时间时间由那段地形决定平地t0秒泥坑t1秒加速垫t2秒你可以做两种操作正常往前走一步整个塔一起从 x 走到 x1花费对应地形的时间。超级扔蛋只能用于高度 ≥ 2 的塔最底下的那个蛋比如一开始的 A留在原地消失。它上面的所有蛋比如 B、C、D一次性飞到前面d距离处但不能超过终点 l。这个操作不花时间0秒而且飞过去的蛋仍然保持原来的上下顺序。目标让最顶上的蛋 D到达终点坐标l问最少需要多少秒。题目思路这是一道最短路径问题但由于状态转移具有单向性位置只增不减可以转化为DAG上的动态规划。定义dp状态 dp[j][x] 表示在位置x塔的高度为j有j个蛋时的最短时间其中dp[4][0] 0;接着按照位置从小到达进行状态转移即可转移分2种一是正常前行二是超级起步最后遍历到达l后每种蛋的剩余数的dp[j][l]即可找到最小值代码如下#include bits/stdc.h using namespace std; using i128 __int128; #define int long long #define endl \n const int INF (1LL 62); void solve() { int l, d; cin l d; int t0, t1, t2; cin t0 t1 t2; string S; cin S; // cost[i] 对应第i段 (0-index)从坐标i到i1的代价 vectorint cost(l); for (int i 0; i l; i) { if (S[i] 0) cost[i] t0; else if (S[i] 1) cost[i] t1; else cost[i] t2; } // dp[j][x] 表示在位置x塔的高度为j有j个蛋时的最短时间 // j: 1..4, x: 0..l vectorvectorint dp(5, vectorint(l 1, INF)); dp[4][0] 0; // 初始状态4个蛋在位置0 // 按位置从小到大遍历 // 因为所有转移都是向前x增加或不变所以这是拓扑序 for (int x 0; x l; x) { for (int j 1; j 4; j) { if (dp[j][x] INF) continue; // 转移1: 正常前进整个塔一起走一步 // 从x走到x1代价由地形决定 dp[j][x 1] min(dp[j][x 1], dp[j][x] cost[x]); // 转移2: 超级起步扔蛋 // 条件至少2个蛋才能扔 // 最下面的蛋留在原地消失上面的j-1个蛋飞到min(l, xd) // 代价为0 if (j 2) { dp[j - 1][min(l, x d)] min(dp[j - 1][min(l, x d)], dp[j][x]); } } } // 答案到达位置l时任意高度都可以 // 因为只要最顶端的蛋D到达l就算成功 int ans INF; for (int j 1; j 4; j) ans min(ans, dp[j][l]); cout ans endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T1; //cin T; while (T--) { solve(); } return 0; }