公司动态

8.24【A】

📅 2026/8/26 15:04:19
8.24【A】
1872每次选择至少合并两个石头然后合并实际上就是在得到前缀和目的是让自己得到最多的前缀和对手得到最少的考虑是从正向推还是反向推目前来看貌似可以直接贪心即A直接选择最远的正数好像不行比如到一个前缀和很大的比如100然后下一个是大负数-99那么就是1依然还是正数但不如直接选100然后让这个1给B吃能让分差最大问题转换为在N-1的数组里选数然后让分差最大每个数可以选也可以不选就是状态转移当前选择的收益是总收益减去对手后续选择最大收益但什么是总收益定义DP【i]是从这个位置i开始时A与B的最大分差或者说当前执棋人与对手的最大分差那么最小就是反向开始增长但最后的DP该是什么考虑到最后选了之后就没得选了那么最后的DP应该就是SUM那么如何往前增长前一个的DP可以选也可以不选如果选了那么对手必然只能选最后的考虑到双方选后的分差即DP[cur]sum[cur]-dp[final]如果不选不选是什么情况不选貌似没办法给当前DP赋值解题就是说这里靠对DP定义的重申来解决这个问题DP不仅表示当前位置I时的最好情况也包含了从i开始往后的所有情况的最好情况即DP【i]是后面所有DP的超集那么上面的问题都迎刃而解即当前位置如果选的话那么对手要在后面选那么选的最好情况就是DP{i1】,即后面i1里所有最好的情况就包含在i1上了如果不选那就是要在i1即后面选那么最好的情况也就在i1了class Solution { public: int stoneGameVIII(vectorint stones) { int nstones.size(); vectorintprefix(n,0),dp(n,0); prefix[0]stones[0]; for(int i1;in;i){ prefix[i]prefix[i-1]stones[i]; } dp[n-1]prefix[n-1]; for(int in-2;i0;i--){ dp[i]max(dp[i1],prefix[i]-dp[i1]); } return dp[1]; } };以及最后这个DP在求解的过程中是直接计算的最终量而不是逐渐累积的过程量即DP[CUR]SUM[CUR]-DP[CUR1]是直接算的当前位置所产生的最大分差是一个完全独立的问题与前一个位置与后一个位置的过程完全无关是一次完全独立的计算不会对前后造成影响也没有一个全局量来累计这个过程