题目地址:http://codeforces.com/contest/1176/problem/F

思路:其实就是一个01背包问题,只是添加了回合和每回合的01限制,和每当已用牌数到了10的倍数,那张卡会触发double攻击。

因为卡使用的多少会触发double效果,所以我们要记录攻击的同时记录卡的使用次数,可以由01背包dp[N][N]改变,

第一个维度是当前是第几个回合,第二个维度是记录卡在用了n张的情况下造成的攻击力,但是dp[N][N](N <= 2e5),

占用内存太大显然不行。于是想到用dp[N][10]。

(因为卡的数量可能很多,我们其实只要记录最多三张1费,一张2费,一张3费)
每个回合用卡情况最多3种:
1.用3张一费卡。
2.用2张一费卡,或者1张一费卡,1张二费卡
3.用1张一费卡,或者1张二费卡,或者1张三费卡


 #include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,j,k) for(int i = (j); i <= (k); i++)
#define per(i,j,k) for(int i = (j); i >= (k); i--)
#define mod(x) ((x)%(MOD)) typedef long long LL;
const int MOD = ;
const int N = 2e5 + ;
LL dp[N + ][]; void init(){
rep(i, , N) rep(j, , ) dp[i][j] = -;
} int main(){ ios::sync_with_stdio(false);
cin.tie(); init(); int n;
cin >> n; dp[][] = ;//初始化 rep(o, , n){
int num;
cin >> num; int L1 = ;
int L2 = ;
int L3 = ;
int c1[] = { };//费用1,记录v最大的三张
int c2 = ;//费用2
int c3 = ;//费用3 int c, v;
rep(i, , num){
cin >> c >> v; if (c == ){
if (L1 == ){
int x = ;
if (c1[x] > c1[]) x = ;
if (c1[x] > c1[]) x = ;
if (v > c1[x]) c1[x] = v;
}
else c1[++L1] = v;
}
else if (c == ){
L2 = ;
if (v > c2) c2 = v;
}
else if (c == ){
L3 = ;
if (v > c3) c3 = v;
}
} sort(c1 + , c1 + + ); int max_v = max(c1[], max(c2, c3));//一张v最大的
int _2_1 = c1[];//两张卡费用最大的
int _2_2 = c1[];
if (c2 > _2_2) _2_2 = c2;
if (_2_2 > _2_1) swap(_2_2, _2_1);//两张卡,由1费中间v最大的2张,和一张2费的中间选出v最大的两张
LL _3 = c1[] + c1[] + c1[];//用三张1费 rep(i, , ) dp[o][i] = dp[o - ][i];//先把上个回合的状态保存到当前回合,方便下边的比较
//因为这三种状态都是附加在上个状态下得出的,所以他们之间都是独立的。
//mod(i + x),(i + x >= 10)* value 用于判断是否满足大于等于用的次数是十张的倍数
rep(i, , ){
if (dp[o - ][i] != -){//上个状态是存在的
if (L1 + L2 + L3 >= ){//用的卡牌最少一张的时候,用一张情况 dp[o][mod(i + )] = max(dp[o][mod(i + )],
dp[o - ][i] + max_v + (i + >= )*max_v); }
if (L2 + L1 >= ){//1费2费用的卡牌至少有两张,用两张情况 dp[o][mod(i + )] = max(dp[o][mod(i + )],
dp[o - ][i] + _2_1 + _2_2 + (i + >= )*_2_1); }
if (L1 >= ){//1费卡牌数最少三张,用三张情况 dp[o][mod(i + )] = max(dp[o][mod(i + )],
dp[o - ][i] + _3 + (i + >= )*c1[]); }
}
}
} LL ans = -; //rep(i, 0, n){
// rep(o, 0, 9) cout << dp[i][o] << " ";
// cout << endl;
//}
//cout << endl; rep(o, , ) ans = max(dp[n][o], ans); cout << ans << endl; return ;
}

最新文章

  1. Java(四)
  2. 干货 | Docker文件系统的分层与隔离
  3. HTML5学习之WebWork多线程处理(八)
  4. HDU(2089),数位DP
  5. EF-Code First 入门
  6. PE文件结构详解(二)可执行文件头
  7. 引用Excel时 未在本地计算机上注册ace.oledb.12.0
  8. resin4 简单学习
  9. Yaf框架的配置
  10. AssetBundle实现服务器下载并从本地读取
  11. k8s Docker私有仓库认证
  12. Scala编程基础
  13. scala函数式编程(一)
  14. vue之v-if和v-show
  15. Java10-java语法基础(九)——java的封装性
  16. html5 canvas文本处理
  17. C# 批量上传
  18. 剑指offer-int类型负数补码中1的个数-位操作
  19. 牛客网NOIP赛前集训营-提高组(第六场)B-选择题[背包]
  20. 对TControl和TWinControl相同与不同之处的深刻理解(每一个WinControl就相当于扮演了整个Windows的窗口管理角色,主要是窗口显示和窗口大小)——TWinControl就两个作用(管理子控件的功能和调用句柄API的功能)

热门文章

  1. JS 输入框为空的使用
  2. wpf 换行符
  3. Android零基础入门第12节:熟悉Android Studio界面,开始装逼卖萌
  4. 【Python】:拓展Queue实现有序不重复队列
  5. Visual studio调试Web发生未能正常启动IIS express
  6. 三星860 evo 250g 开启AHCI模式读写对比
  7. Delphi-网络编程-第一个网络方面作品(UDP聊天程序)
  8. Qt中实现单例模式(SingleTon),大约有3种办法
  9. 10 jQuery的事件绑定和解绑
  10. window系统谷歌浏览器百度搜索框光标不能输入并且不显示光标----自制bug以及解决