题目描述餐厅的门有K1K1K1种开度状态000到KKK每分钟可变化111个单位开大、关小或不变。初始时门关着状态000。有NNN个歹徒第iii个歹徒在时刻TiT_iTi​到达具有财富值PiP_iPi​和体型SiS_iSi​。若门在TiT_iTi​时刻的开度恰好等于SiS_iSi​则该歹徒可以进入并贡献PiP_iPi​否则离开。时间范围为[0,T][0, T][0,T]目标是最大化进入的歹徒总财富。输入格式第一行为整数MMM表示数据集个数。每组数据第一行为NNN、KKK、TTT。第二行包含NNN个整数TiT_iTi​。第三行包含NNN个整数PiP_iPi​。第四行包含NNN个整数SiS_iSi​。各组之间用空行分隔。输出格式对于每组数据输出最大总财富。若无人可进入输出000。每组输出之间用空行分隔。样例输入2 4 10 20 10 16 8 16 10 11 15 1 10 7 1 8 2 17 1000 5 0 50 33 6 1输出26 0题目分析本题是一个动态规划问题。时间TTT最大300003000030000门状态KKK最大100100100NNN最大100100100。可以在时间轴上逐步模拟门状态的变化同时累计每个时刻每个门状态下能够获得的财富。关键点门状态在相邻时刻只能变化111不变、加111或减111。若同一时刻有多个歹徒具有相同的(Ti,Si)(T_i, S_i)(Ti​,Si​)他们的财富可累加。转移时当前时刻iii的状态jjj可以从上一时刻i−1i-1i−1的状态j−1j-1j−1、jjj、j1j1j1转移而来并加上当前时刻jjj状态下可获得的财富。解题思路读入所有歹徒数据用二维数组V[time][state]存储每个时刻每个门状态下能获得的总财富因为同一时刻可能有多个歹徒。初始化dp[0][0] 0其余为-1表示不可达。对时间ttt从111到TTT循环对门状态sss从000到KKK循环若dp[t-1][s]可达则尝试转移到当前时刻的状态sss不变、s−1s-1s−1关小、s1s1s1开大并加上对应状态下的财富V[t][new_s]。最后答案取dp[T][s]中的最大值。复杂度分析时间复杂度O(T⋅K)O(T \cdot K)O(T⋅K)T≤30000T \le 30000T≤30000K≤100K \le 100K≤100约3×1063 \times 10^63×106非常快。空间复杂度O(T⋅K)O(T \cdot K)O(T⋅K)可优化为滚动数组但本题30000×101≈3×10630000 \times 101 \approx 3 \times 10^630000×101≈3×106个整数约121212MB可接受。代码实现// Gangsters// UVa ID: 672// Verdict: Accepted// Submission Date: 2018-09-23// UVa Run Time: 0.080s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structgangster{intti,pi,si;};intdp[30001][101],V[30001][101];intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intM,N,K,T;gangster G[101];cinM;for(intcs1;csM;cs){cinNKT;for(inti0;iN;i)cinG[i].ti;for(inti0;iN;i)cinG[i].pi;for(inti0;iN;i)cinG[i].si;for(inti0;iT;i)for(intj0;jK;j){dp[i][j]-1;V[i][j]0;}for(inti0;iN;i)V[G[i].ti][G[i].si]G[i].pi;dp[0][0]0;for(inti1;iT;i)for(intj0;jK;j)if(~dp[i-1][j]){dp[i][j]max(dp[i][j],dp[i-1][j]V[i][j]);if(j)dp[i][j-1]max(dp[i][j-1],dp[i-1][j]V[i][j-1]);if(jK)dp[i][j1]max(dp[i][j1],dp[i-1][j]V[i][j1]);}if(cs1)cout\n;intmaximum0;for(inti0;iK;i)maximummax(maximum,dp[T][i]);coutmaximum\n;}return0;}总结本题通过动态规划在时间轴上模拟门状态的变化同时累计财富。关键点包括将同一时刻同一状态的歹徒财富合并。状态转移时考虑门状态的三种变化不变、加111、减111。注意初始状态dp[0][0]0dp[0][0] 0dp[0][0]0不可达状态用−1-1−1表示。该解法是经典的时间依赖动态规划适用于状态转移规则简单的场景。