8.20
T1
题目大意：
给定一个数组，每次操作可以删掉一个数
正解:
用一个计数数组记录每个数的个数，然后循环找到每个数得到的贡献，就用dp实现，它是上一个数得到的贡献(不计算这个数的贡献)和上上个数得到的贡献+这个数增加的贡献(他的个数乘这个数)的最大值，最后取所有dp的最大值就可以。
T2
题目大意：
给定若干个数组，每个数组有若干个数，能选取m个数，每个数组只能从左右端点选取，选取后消失，每选取一个数就会增加这么多的贡献，求做大贡献。
原思路:
直接贪心，启用优先队列来维护最大值，再用deque数组存储每个数组，然后每找到一个就删一个再将新的数压入堆。
正解:
先算出每一个数组的总和，然后维护第i个数组取走j个数最大贡献，f[i][j]是所有从左边取 l 个物品的总价值+从右边取j - l个物品的总价值的最大值。
然后维护前i个数组取走j个数的最大贡献。
dp[i][j]=最大的前i-1个数取走j-k(j,k通过枚举)个的最大贡献，加上第i个数组取走k个数最大贡献。
T3
题目大意：
有若干个数，每次选m个数，本身有贡献，有k个关系，先选x再选y能获得一些贡献，求最大贡献
原思路:
把这个关系用来建图，每个点本身有点权，如果有关系就连一个边权为额外增加的边，否则连一个边权为0的边
正解:
暴力的思路是回溯，但O(n!)n<=12才能过，于是想到能优化回溯的状压(O(
dp[i][j]:第i种状态，上一步是j。
枚举每种情况，然后再枚举每种可能从哪里转移的情况找最大的第i去掉j这一位的状态，上一步是k再加上原本的点权和通过关系获得的一些贡献。
T4
题目大意：
给定一个合法的括号序列
要给一些括号标记，要满足一些条件：
1，每个括号要么不标记，要么标1，要么标2
2.对于任意一对匹配的括号，必须恰好有一个被标记
3.相邻的两个已标记括号不能同色
正解:
先求出所有左括号能配对的右括号的编号，然后枚举1和n的标记情况，然后记忆化搜索，求出总和。
搜索就是区间dp，先看有没有来过，如果来过直接return。
没来过就判断左右端点匹配不匹配，如果匹配看符不符合要求，不符合要求这一个就是0，符合要求且长度为二就只有一种情况，其余情况l,r往里缩，也是枚举标记情况然后dfs，但是要看是否符合要求。
如果不匹配就枚举标记情况，要看是否符合要求，然后总和是l到l能匹配到的编号*l能匹配到的编号后一个编号到r