当前位置: 首页 > news >正文

洛谷P9676 [ICPC 2022 Jinan R] Skills

洛谷P9676 [ICPC 2022 Jinan R] Skills

P9676 [ICPC 2022 Jinan R] Skills

设计状态时,可以知道要用当前的压掉一维,\(dp_{i,j,0/1/2}\) 表示当前选第 \(0/1/2\) 种,\(i,j\) 表示其余两种的最后选择时间。

如果没有 \(0\) 的限制,我们可以很自然的看出 \(DP\) 方程。

首先,上次选的,这次也选。

// cur表示时间,now是cur&1
dp[now^1][i][j][0] = max(dp[now^1][i][j][0],dp[now][i][j][0]-(i?cur-i+1:0)-(j?cur-j+1:0)+val[cur+1][0]);
dp[now^1][i][j][1] = max(dp[now^1][i][j][1],dp[now][i][j][1]-(i?cur-i+1:0)-(j?cur-j+1:0)+val[cur+1][1]);
dp[now^1][i][j][2] = max(dp[now^1][i][j][2],dp[now][i][j][2]-(i?cur-i+1:0)-(j?cur-j+1:0)+val[cur+1][2]);

然后,上次选的,这次不选,一共 \(9\) 种。

dp[now^1][cur][j][1] = max(dp[now^1][cur][j][1],dp[now][i][j][0]-(j?cur-j+1:0)-1+val[cur+1][1]);
dp[now^1][cur][i][2] = max(dp[now^1][cur][i][2],dp[now][i][j][0]-(i?cur-i+1:0)-1+val[cur+1][2]);
dp[now^1][cur][j][0] = max(dp[now^1][cur][j][0],dp[now][i][j][1]-(j?cur-j+1:0)-1+val[cur+1][0]);
dp[now^1][i][cur][2] = max(dp[now^1][i][cur][2],dp[now][i][j][1]-(i?cur-i+1:0)-1+val[cur+1][2]);
dp[now^1][j][cur][0] = max(dp[now^1][j][cur][0],dp[now][i][j][2]-(j?cur-j+1:0)-1+val[cur+1][0]);
dp[now^1][i][cur][1] = max(dp[now^1][i][cur][1],dp[now][i][j][2]-(i?cur-i+1:0)-1+val[cur+1][1]);

再来一个性质,一个练习不可能掉成 \(0\),否则不如一开始就给其他练习。

距离上一次不会超过 \(200\) 天。

做完了,时复 \(O(n\max{a_{i,j}})\)

\(\Large \mathscr{Code}\)

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int T,n,m,val[N][4],dp[2][N][N][3],ans;
inline void DP(int cur,int i,int j){int now = cur&1;dp[now^1][i][j][0] = max(dp[now^1][i][j][0],dp[now][i][j][0]-(i?cur-i+1:0)-(j?cur-j+1:0)+val[cur+1][0]);dp[now^1][i][j][1] = max(dp[now^1][i][j][1],dp[now][i][j][1]-(i?cur-i+1:0)-(j?cur-j+1:0)+val[cur+1][1]);dp[now^1][i][j][2] = max(dp[now^1][i][j][2],dp[now][i][j][2]-(i?cur-i+1:0)-(j?cur-j+1:0)+val[cur+1][2]);dp[now^1][cur][j][1] = max(dp[now^1][cur][j][1],dp[now][i][j][0]-(j?cur-j+1:0)-1+val[cur+1][1]);dp[now^1][cur][i][2] = max(dp[now^1][cur][i][2],dp[now][i][j][0]-(i?cur-i+1:0)-1+val[cur+1][2]);dp[now^1][cur][j][0] = max(dp[now^1][cur][j][0],dp[now][i][j][1]-(j?cur-j+1:0)-1+val[cur+1][0]);dp[now^1][i][cur][2] = max(dp[now^1][i][cur][2],dp[now][i][j][1]-(i?cur-i+1:0)-1+val[cur+1][2]);dp[now^1][j][cur][0] = max(dp[now^1][j][cur][0],dp[now][i][j][2]-(j?cur-j+1:0)-1+val[cur+1][0]);dp[now^1][i][cur][1] = max(dp[now^1][i][cur][1],dp[now][i][j][2]-(i?cur-i+1:0)-1+val[cur+1][1]);
}
inline void work(){cin>>n;ans = 0;for(int i=1;i<=n;i++){cin>>val[i][0]>>val[i][1]>>val[i][2];}memset(dp,-0x3f,sizeof(dp));dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;for(int cur=0;cur<n;cur++){int now = cur&1;for(int i=max(0,cur-201);i<=cur;i++){for(int j=max(0,cur-201);j<=cur;j++){memset(dp[now^1][i][j],-0x3f,sizeof(dp[now^1][i][j]));}}for(int i=max(0,cur-201);i<=cur;i++){memset(dp[now^1][0][i],-0x3f,sizeof(dp[now^1][0][i]));}for(int i=max(0,cur-201);i<=cur;i++){memset(dp[now^1][i][0],-0x3f,sizeof(dp[now^1][i][0]));}memset(dp[now^1][0][0],-0x3f,sizeof(dp[now^1][0][0]));for(int i=max(0,cur-201);i<=cur;i++){for(int j=max(0,cur-201);j<=cur;j++){DP(cur,i,j);}}for(int i=max(0,cur-201);i<=cur;i++){DP(cur,0,i);}for(int i=max(0,cur-201);i<=cur;i++){DP(cur,i,0);}DP(cur,0,0);}for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){ans = max({ans,dp[n&1][i][j][0],dp[n&1][i][j][1],dp[n&1][i][j][2]});}}cout<<ans<<'\n';
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>T;while(T--) work();return 0;
}
http://www.hskmm.com/?act=detail&tid=24681

相关文章:

  • 读人形机器人31未来30年
  • 【java面试】redis篇 - 指南
  • 洛谷P8421 [THUPC 2022 决赛] rsraogps
  • NLP学习路线图(十四):词袋模型(Bag of Words) - 详解
  • 实用指南:苍茫命令行:linux模拟实现,书写微型bash
  • 2025 年压滤机厂家最新推荐排行榜:隔膜压滤机,污泥压滤机,真空压滤机,板框压滤机,带式压滤机优质企业权威评选及选购指南
  • 2025 年搅拌器厂家最新推荐排行榜:涵盖立式、不锈钢、侧入式等多类型设备,深度解析实力厂商
  • 2025 年最新推荐承烧板厂家排行榜:筛选优质企业,破解采购难题,赋能高温工业生产
  • 一文看懂AI SoC芯片
  • 月球尘埃电解技术实现资源就地利用
  • 漏洞赏金计划公开后的三个阶段与应对策略
  • Python 在科学计算与工程模拟中的应用
  • Python 在大数据与分布式计算中的应用
  • Python 在教育与科研中的应用与价值
  • Python 在自动化测试与质量保障中的应用
  • 玩转树莓派屏幕之三:lvgl移植到树莓派
  • enthalpy/entropy
  • Day26自定义异常
  • 谈谈redis的热key问题如何解决
  • Stimulsoft 引入无代码脚本编程 —— Blockly 让报表与仪表盘更智能
  • 理解、学习与使用 Java 中的 Optional
  • 211 粉了整个小 QA 吧
  • 玩转树莓派屏幕之二:自定义屏幕显示
  • INFINI Labs 产品更新 - Coco AI v0.8 与 Easysearch v1.15 全新功能上线,AI 搜索体验再进化!
  • 玩转树莓派屏幕之一:LCD屏幕显示
  • Python离群值检测实战:使用distfit库实现基于分布拟合的异常检测
  • 10.4 闲话
  • 神秘专题训练之老题补做
  • 全球 whk 水平下降 998244353 倍,而你不变
  • 202510做题记录