首页 > 其他分享 >P6879 [JOI 2020 Final] スタンプラリー 3 [区间DP]

P6879 [JOI 2020 Final] スタンプラリー 3 [区间DP]

时间:2024-11-05 11:11:00浏览次数:3  
标签:P6879 int ll 2020 dp 端点 区间 JOI DP

P6879 [JOI 2020 Final] スタンプラリー 3

Solution

  • 首先这是一道最优值问题,再根据数据范围 \(n\le 200\),那么正解可能会是 \(O(n^3)\) 的 DP。

  • 根据题意,我们发现主角走过的雕像一定是个区间,可以考虑区间DP。

  • 想一想我们需要知道什么,然后把它放到 DP 状态里面。我们需要知道主角走过的是哪段区间,以及当前的时间,那么主角当前位置如何确定呢,并不需要枚举区间中的每个点,因为,如果他已经走完一段区间并且停留在端点上,那他下一次要去的位置肯定在端点外的一格,不会停留在区间里面。因此我们只需要知道他当前在左端点还是右端点即可,这是区间 DP 的一个经典套路。

  • 由于 \(T\le 10^9\),显然复杂度是和值域无关的,如果我们记录当前时间,那状态数肯定会炸。于是又有一个经典套路,DP 状态的值域和定义域互换。定义域就是当前时间,值域显然就是当前收集到的数量,原本是当前时间能收集到的最大数量,互换了之后,我们可以记录当前收集了多少个雕像,需要的最小时间。由于答案不会超过 \(n\),那么这样是可行的。

  • 设 \(f_{l,r,k,0/1}\) 表示当前从原点出发,顺时针走过了 \(l\) 个雕像,逆时针走过了 \(r\) 个雕像,一共收集了 \(k\) 个雕像,当前位置在左端点还是右端点,的最小时间。

  • 转移很简单,例如,\(f_{l,r,k,0}\to f_{l+1,r,k+[f_{l,r,k,0/1}+x_{l+1}-x_l\ \le \ t_{l+1}],0}+x_{l+1}-x_l\)。

  • 状态数是 \(O(n^3)\) 的,转移是 \(O(1)\),于是时间复杂度 \(O(n^3)\)。

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int N = 2e2 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n;
ll L, x[N], t[N], dp[N][N][N][2]; // 0 左边,1 右边
int ans = 0;

void Min(ll &a, ll b) {a = min(a, b);}

int main() {
    cin >> n >> L;
    for (int i = 1; i <= n; i++) cin >> x[i];
    x[n + 1] = L;
    for (int i = 1; i <= n; i++) cin >> t[i];
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0][0] = dp[0][0][0][1] = 0;
    for (int l = 0; l <= n; l++) {
        for (int r = 0; l + r <= n; r++) {
            for (int k = 0; k <= l + r; k++) {
                int tmp;
                if (dp[l][r][k][0] != inf) {
                    tmp = (dp[l][r][k][0] + x[l + 1] - x[l]) <= t[l + 1];
                    Min(dp[l + 1][r][k + tmp][0], dp[l][r][k][0] + x[l + 1] - x[l]);
                    tmp = (dp[l][r][k][0] + L - x[n - r] + x[l]) <= t[n - r];
                    Min(dp[l][r + 1][k + tmp][1], dp[l][r][k][0] + L - x[n - r] + x[l]);
                    ans = max(ans, k);
                }
                if (dp[l][r][k][1] != inf) {
                    tmp = (dp[l][r][k][1] + x[n - r + 1] - x[n - r]) <= t[n - r];
                    Min(dp[l][r + 1][k + tmp][1], dp[l][r][k][1] + x[n - r + 1] - x[n - r]);
                    tmp = (dp[l][r][k][1] + L - x[n - r + 1] + x[l + 1]) <= t[l + 1];
                    Min(dp[l + 1][r][k + tmp][0], dp[l][r][k][1] + L - x[n - r + 1] + x[l + 1]);
                    ans = max(ans, k);
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

标签:P6879,int,ll,2020,dp,端点,区间,JOI,DP
From: https://www.cnblogs.com/chenwenmo/p/18527489

相关文章

  • left join 出现重复on导致sql语句报错
    leftjoin出现重复on导致sql语句报错​mybatis-plus开启多租户插件功能时,在进行链表查询时会重复出现on导致sql语句报错原因​原因是引入的分页拆件中的jsqlparser解析器和mybatis-plus的jsqlparser解析器冲突了,导致默认采用了分页拆件的jsqlparser解析器​分页拆件......
  • 第三十三讲:到底可不可以使用join?
    第三十三讲:到底可不可以使用join?简概:厌烦了平淡的开头提出问题​ 在实际生产中,关于join语句使用的问题,一般会集中在以下两类:我们DBA不让使用join,使用join有什么问题呢?如果有两个大小不同的表做join,应该用哪个表做驱动表呢?提出示例​ 今天这篇文章,我就先跟你说......
  • JOI Open 2019 Triple Jump 题解
    原题链接可以暴力枚举\(a,b\),然后\(c\in[2b-a,n]\),找区间最大值即可。对于我们选择的\(a,b\)间,若能在\((a,b)\)中找到某个下标\(i\),满足\(h_i\geh_a\)或\(h_i\geh_b\),那么选择\(i\)是更优的。理由很简单,无论是从\(a\toi\)还是从\(b\toi\),都会扩大\(c\)的......
  • [ACTF2020 新生赛]BackupFile
    题目链接:https://buuoj.cn/challenges#[ACTF2020新生赛]BackupFile打开环境后如下。题目中仅有一句"Trytofindoutsourcefile!"的提示,因此直接扫描一下备份文件,发现存在"index.php.bak"文件,该文件代码如下所示。<?phpinclude_once"flag.php";if(isset($_GET['key......
  • [BJDCTF2020]Easy MD5
    题目链接:https://buuoj.cn/challenges#[BJDCTF2020]EasyMD5打开环境后如下所示。响应包如下。HTTP/1.1200OKServer:openrestyDate:Fri,25Oct202415:20:01GMTContent-Type:text/html;charset=UTF-8Connection:keep-aliveVary:Accept-EncodingX-Powered-By:......
  • [MRCTF2020]你传你呢
    题目链接:https://buuoj.cn/challenges#[MRCTF2020]你传你......
  • [ACTF2020 新生赛]Upload
    题目链接:https://buuoj.cn/challenges#[ACTF2020新生赛]Upload打开环境后如下所示。指向灯泡,可以发现存在一个上传功能。尝试先上传".php"后缀文件,响应包如下。题目提示"nonono~Badfile!",此处笔者直接修改后缀为".phtml"后,发现可以成功上传,并且网页告知了上传的文件......
  • [ACTF2020 新生赛]Include
    链接:https://buuoj.cn/challenges#[ACTF2020新生赛]Include。打开环境后如下,只有一个"tips"的超链接。访问tips,留意传入了"file"参数。接下来,可以尝试下路径穿越:?file=flag.php../../../../../etc/passwd。可以看到,存在路径穿越漏洞,但是通过路径穿越漏洞并没有读取到......
  • [ACTF2020 新生赛]Exec
    题目链接:https://buuoj.cn/challenges#[ACTF2020新生赛]Exec。打开后,环境如下。尝试输入"127.0.0.1",抓取请求包。POST/HTTP/1.1Host:038dc28f-5191-4958-8946-1127f62ad770.node5.buuoj.cn:81Content-Length:16Cache-Control:max-age=0Upgrade-Insecure-Requests:......