第1题最大子段和洛谷P1115)很简单的动态规划问题dp[i]表示以i为右边界时子段的最大值。现在确定状态转移那就看dp[i-1]喽它要是负数就是个累赘带它干嘛。以下是代码#includeiostream #includequeue using namespace std; int dp[200000] {0}; int main() { int n; int max -10000; int a; cin n; for (int i 1; i n; i) { cin a; dp[i] (dp[i - 1] a 0 ? dp[i - 1] a : a); max (max dp[i] ? max : dp[i]); } cout max; return 0; }第2题 采药P1048这道题就是01背包直接看代码#includeiostream #includequeue using namespace std; int dp[1001] {0}; int arr[101][2]; int main() { int t, m; cin t m; for (int i 1; i m; i) { cin arr[i][0] arr[i][1]; } for (int i 1; i m; i) { for (int j t; j arr[i][0]; j--) { dp[j] max(dp[j], dp[j - arr[i][0]] arr[i][1]); } } cout dp[t]; return 0; }第3题宝物筛选洛谷P1776这道题相比于上一道不同之处在于宝物是可以多件的朴素地想我们直接把n件一样的宝物拆开成一件件不就可以了吗这在宝物件数不多的情况下是可行的。但这题宝物件数可以到100000显然是会超时的。那么还能怎么拆分呢我们为啥要把宝物拆成1件1件的呢当然是为了让它可以在1~ n间任意件都有被选择的机会所以我们拆分的方法要是能构成1~n所有的数就可以了而2进制是个好东西啊它就满足条件。具体看以下代码#includeiostream #includequeue using namespace std; int dp[40001] {0}; int v[1701];//价值 int w[1701];//重量 int main() { int n,ww; cin n ww; int v1, w1, m1; int num 1; for (int i 1; i n; i) { cin v1 w1 m1; int k 1; while (m1 k) { v[num] k * v1; w[num] k * w1; m1 - k; k * 2; num; } if (m1) { v[num] m1 * v1; w[num] m1 * w1; num; } } for (int i 1; i num; i) { for (int j ww ; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } cout dp[ww]; return 0; }第4题最长公共子序列洛谷P1439)这题呢用类似01背包动态规划的方法复杂度会是n^2,数据到了100000所以会超时。对于两个排列要找其公共子序列我们如果拿出其中一个排列出来将它一一对应映射成一个从1排到n的排列那么问题就转换成在一个序列中找到最长的升序子序列注意要把原来的值变换成映射的值。那么如何找到最长升序子序列呢我们用sign[i]表示目前为止升序子序列长度为i时序列尾部的值当一个新来的数要加入时如果它比现存的sign都大的话自然而然就加在最后了记录最长值的变量值要加1但是如果sign里有比它大的呢当然是置换掉第1个比它大的啦因为它不能越过比它大的值。那为啥要置换呢因为这样后面的数才比较容易越过去啊。具体代码如下#includeiostream #includequeue using namespace std; int a[100001] { 0 }; int b[100001] { 0 }; int jud[100001] { 0 }; int sign[100001] { 0 }; int main() { int n; cin n; for (int i 1; i n; i) { cin a[i]; jud[a[i]] i; } for (int i 1; i n; i) { cin b[i]; } int num 0; for (int i 1; i n; i) { if (jud[b[i]] sign[num]) { num; sign[num] jud[b[i]]; } else { int ans 0; int l 1; int r num; int mid; while (l r) { mid (l r) / 2; if (sign[mid] jud[b[i]]) { ans mid; r mid - 1; } else { l mid 1; } } sign[ans] jud[b[i]]; } } cout num; return 0; }第5题Kevin and Puzzle对于这道题每个人都可能有2种状态那我们考虑方程dp[n][2],那dp[i][0]和dp[i][1]表示啥含义呢我们的目标是得到游戏配置的数量而最后1个人只有诚实和骗子两种状态所以如果dp[i][0]表示为前i个人参与并且第i个人是骗子的游戏配置数量 dp[i][1]表示为前i个人参与并且第i个人是诚实的游戏配置数量那么最终答案可表示为dp[n][0]dp[n][1]。状态转移我们知道骗子不能相邻所以dp[i][0]dp[i-1][1]。那dp[i][1]呢对于第i人是诚实的第i-1人可以是骗子也可以是诚实的所以dp[i][1]可能等于0或dp[i-1][0]或dp[i-1][1]或dp[i-1][0]dp[i-1][1],那就要看我们所得到的数据是否满足dp[i-1][0]或dp[i-1][1]被加入的必要条件如果第i-1人诚实那么arr[i]arr[i-1]肯定成立如果i-1骗子则i-2是诚实的那么arr[i]arr[i-2]1肯定成立。那既然状态能够转移那就确定一下初始状态dp[1][0]1(因为骗子说啥都可以而dp[1][1]因为第1个人得说0个才能是诚实的所以当arr[1]0时dp[1][1]才为1否则为0。具体代码如下#includeiostream #includequeue #define MOD 998244353 using namespace std; int arr[200001] { 0 }; int dp[200001][2] { 0 }; int main() { int t; cin t; int n; for (int i 0; i t; i) { cin n; for (int j 1; j n; j) { cin arr[j]; } dp[1][0] 1; dp[1][1] 0; if (!arr[1]) { dp[1][1] 1; } for (int j 2; j n; j) { dp[j][0] dp[j - 1][1]; dp[j][1] 0; if (arr[j] arr[j - 2] 1) { dp[j][1] dp[j - 1][0]; } if (arr[j] arr[j - 1]) { dp[j][1] (dp[j - 1][1]dp[j][1])%MOD; } } cout (dp[n][1] dp[n][0]) % MOD endl; } return 0; }第6题World is Mine要先分析两个人的最优策略贪心地alice肯定尽可能地去吃最小的而bob要保证自己吃到的alice吃不到这才能减少alice吃的数量所以把bob看成能够积累吃的个数然后在他的回合它可以选择把所有吃的机会用掉或者不用。dp[i][j]表示前i种蛋糕bob吃了j个蛋糕的情况下alice能吃到的最少蛋糕数。具体代码如下#includeiostream #includevector using namespace std; int main() { int t; cin t; int n; for (int p 0; p t; p) { cin n; vectorintarr(n 1), cnt(n 1); for (int j 0; j n; j) { cin arr[j]; cnt[arr[j]]; } vectorvectorintdp(n 1, vectorint(n 1, 1e5)); dp[0][0] 0; for (int i 1; i n; i) { for (int j 0; j n / 2; j) { if (!cnt[i]) { dp[i][j] dp[i - 1][j]; continue; } if (j cnt[i] n / 2 j cnt[i] dp[i - 1][j]) { dp[i][j cnt[i]]dp[i - 1][j]; } dp[i][j] min(dp[i][j], dp[i - 1][j] 1); } } int min1 1e5; for (int j 0; j n / 2; j) { min1 min(min1, dp[n][j]); } cout min1 endl; } return 0; }