CF E. Destroy it!
题目大意
有 n 个回合，每个回合会获得若干张卡牌，每张牌有费用 ci∈{1,2,3} 和伤害 di。在每个回合中，你可以选择一些牌打出，但总费用不能超过 3。未打出的牌在本回合结束后丢弃。另外，有一个神器效果：你打出的第 10 张牌（即累计第 10、20、…张）造成双倍伤害。求 nn 个回合能造成的最大总伤害。
数据范围：n≤2×105，所有回合的卡牌总数 ∑ki≤2×105，di≤109
分析
每个回合独立，但累计打出牌数会影响翻倍时机，因此需要记录当前已打出的牌数模 10。
由于费用只有 1、2、3，每回合可选的出牌组合有限，可以枚举所有可能的组合（费用和不超过 3）：
打 1 张费用 1 的牌
打 2 张费用 1 的牌
打 3 张费用 1 的牌
打 1 张费用 2 的牌
打 1 张费用 2 和 1 张费用 1 的牌（总费用 3）
打 1 张费用 3 的牌
对于每种组合，我们需要从该回合的牌中选出伤害最大的若干张（因为伤害为正，肯定选大的），并考虑翻倍收益。由于翻倍只发生在累计第 10 的倍数张，且每回合最多打 3 张，我们可以用当前累计模数 jj 和本回合牌数 kk 来判断是否存在一张牌会翻倍：存在翻倍当且仅当 j+k≥10j+k≥10（因为 j<10j<10，此时存在某个 p=10−j≤kp=10−j≤k 使得第 pp 张牌翻倍）。最优策略是将伤害最大的牌放在那个翻倍的位置，从而让最大牌享受双倍伤害，其余牌不加倍。因此，对于每种组合，我们只需将最大的牌乘以 2（如果存在翻倍），其余牌直接相加，即可得到该组合在本回合的伤害。
Solution
标签：动态规划，贪心
状态定义
设 dp[i][j] 表示前 i个回合结束后，累计打出的牌数模 10 等于 j时的最大总伤害。初始化 dp[0][0]=0d，其余为 −1表示不可达。
每回合处理
对于第 i个回合：
- 读入该回合的所有牌，按费用分为三组（费用 1、2、3），每组内按伤害降序排序，以便快速取最大几张。
- 首先，本回合可以不出牌，因此将上一回合的所有状态直接复制到当前回合：dp[i][j]=dp[i−1][j]（包括不可达状态也复制，但实际只有非负值有意义）。
- 枚举所有可能的出牌组合，对于每种组合，根据当前已打牌数 j 更新状态。每种组合的计算方式如下（假设当前组合打 k 张牌，且按降序取相应费用下的最大伤害值）：
打 1 张费用 1：取最大伤害 a，伤害 = a×(j+1≥10?2:1)，新模数 = (j+1)%10。
打 2 张费用 1：取最大 a 和次大 b，伤害 = b+a×(j+2≥10?2:1)，新模数 = (j+2)%10。
打 3 张费用 1：取前三大的 a≥b≥c，伤害 = c+b+a×(j+3≥10?2:1)，新模数 = (j+3)%10。
打 1 张费用 2：取最大 aa，伤害 = a×(j+1≥10?2:1)，新模数 = (j+1)%10
打 1 张费用 2 和 1 张费用 1：取费用 2 的最大 a 和费用 1 的最大 b，令 a≥b（否则交换），伤害 = b+a×(j+2≥10?2:1)，新模数 = (j+2)%10。
打 1 张费用 3：取最大 a，伤害 = a×(j+1≥10?2:1)，新模数 = (j+1)%10。
对于每种组合，仅当上一回合对应状态 dp[i−1][j] 非负时进行转移，取最大值更新 dp[i][新模数]。
最终答案
遍历所有模数 j=0….9，取 dp[n][j] 的最大值即为答案。
时间复杂度
每回合枚举的组合数常数级（最多 6 种），每种组合遍历 10 种模数，总复杂度 O(n×10×6)=O(n)
每回合的牌需要排序，总牌数不超过 2×1e5，排序总复杂度 O(∑kilogki)，可轻松通过。
代码逻辑说明
使用二维数组 dp[i][j] 存储状态，初始化为 -1，dp[0][0]=0。
每回合读入所有牌，按费用存入三个向量并降序排序。
首先将上一行的 dp 值复制到当前行（对应不出牌的情况）。
然后依次检查每种组合是否有足够的牌，若有则计算伤害并更新。
注意在组合 5 中，需要将较大的那张牌放在可能翻倍的位置，因此取两者较大者乘以翻倍因子。
最后输出所有 dp[n][j]的最大值。
该算法通过枚举所有可能的出牌组合，结合模 10 状态，正确地计算了最优伤害。
下面是代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0)
#define pll pair<ll,ll>bool comp(ll a, ll b){return a > b;
}
void solve(){ll n; cin >> n;vector<vector<ll> > dp(n + 1, vector<ll> (10,-1));dp[0][0] = 0;for(ll i = 1; i <= n; i++){vector<vector<ll> > aa(4);ll ct; cin >> ct;for(ll j = 1; j <= ct; j++){ll a,b; cin >> a >> b;aa[a].push_back(b);}for(ll j = 1; j <= 3; j++){sort(aa[j].begin(),aa[j].end(),comp);}ll l1 = aa[1].size(), l2 = aa[2].size(), l3 = aa[3].size();for(ll j = 0; j <= 9; j++){dp[i][j] = dp[i - 1][j];//统一全部继承了，负数也继承}//不影响从【0】[0]开始if(l1 >= 1){//打1for(ll j = 0; j <= 9; j++){if(dp[i - 1][j] < 0) continue;ll dem = aa[1][0] * (j + 1 >= 10 ? 2 : 1);ll nj = (j + 1) % 10;dp[i][nj] = max(dp[i][nj],dp[i - 1][j] + dem);}}if(l1 >= 2){for(ll j = 0; j <= 9; j++){if(dp[i - 1][j] < 0) continue;ll dem = aa[1][1] + aa[1][0] * (j + 2 >= 10 ? 2 : 1);ll nj = (j + 2) % 10;dp[i][nj] = max(dp[i][nj],dp[i - 1][j] + dem);}}if(l1 >= 3){for(ll j = 0; j <= 9; j++){if(dp[i - 1][j] < 0) continue;ll dem = aa[1][2] + aa[1][1] + aa[1][0] * (j + 3 >= 10 ? 2 : 1);ll nj = (j + 3) % 10;dp[i][nj] = max(dp[i][nj],dp[i - 1][j] + dem);}}if(l2 >= 1){for(ll j = 0; j <= 9; j++){if(dp[i - 1][j] < 0) continue;ll dem = aa[2][0] * (j + 1 >= 10 ? 2 : 1);ll nj = (j + 1) % 10;dp[i][nj] = max(dp[i][nj],dp[i - 1][j] + dem);}}if(l2 >= 1 && l1 >= 1){for(ll j = 0; j <= 9; j++){if(dp[i - 1][j] < 0) continue;ll a = max(aa[1][0],aa[2][0]), b = min(aa[1][0],aa[2][0]);ll dem = b + a * (j + 2 >= 10 ? 2 : 1);ll nj = (j + 2) % 10;dp[i][nj] = max(dp[i][nj],dp[i - 1][j] + dem);}}if(l3 >= 1){for(ll j = 0; j <= 9; j++){if(dp[i - 1][j] < 0) continue;ll dem = aa[3][0] * (j + 1 >= 10 ? 2 : 1);ll nj = (j + 1) % 10;dp[i][nj] = max(dp[i][nj],dp[i - 1][j] + dem);}}}ll ans = 0;for(ll i = 0; i <= 9; i++){ans = max(ans,dp[n][i]);}cout<<ans<<endl;return;
}
int main(){fast;ll t = 1; //cin >> t;while(t--){solve();}return 0;
}