10.29解题报告3

· · 个人记录

T3:逛公园

Description
策策由于在noip2017考试当天去逛公园了，没能出现在考场上，转眼到了noip2018，策策的公园也悄然转变，策策能否克服诱惑，成功坐在考场上呢？
问题描述
策策同学特别喜欢逛公园，公园可以看做有n个景点的序列，每个景 点会给策策带来di 的愉悦度，策策初始有x0 的愉悦度，然而愉悦度也是有上限的，他在每个景点的愉悦度上限为li ，策策想要从 l 到 r这一段景点中选择一段景点参观(从这一段的左端点逛到这一段的右端点)，策策想知道他最终的愉悦度的最大值是多少，你能帮帮他吗？(区间可以为空，也就是说答案最小为x0 )
Input
第一行两个数n,q 表示景点序列长度 和 询问个数
第二行n个数 表示di
第三行n个数 表示li
接下来q行，每行3个数：
表示l,r,x0，下标均从1开始

这是一道不错(哲学)的分块暴力题，最开始在考场上手慌了，打了个四重循环，枚举区间再暴力检验，结果发现dalao们的暴力都是如此优雅：

O(qn)暴力 从 l 循环到 r，每次的起始值都是逛完上个景点的最大值和 X0 的最大值 这样对于每个询问都能 O(n)得答案
（如果您写的足够优秀甚至能过掉后面的很多点）

老天啊，可怜可怜我这个暴力都不会写的苦命娃吧！

代码（85分）：

#include"cstdio"
using namespace std;
const int maxn=40010;
int n,m,k,l,r,ans;
int a[maxn],b[maxn],c[maxn],d[maxn];
inline int minn(int x,int y)
{
    return x<y?x:y;
}
inline int maxx(int x,int y)
{
    return x>y?x:y;
}
int main()
{
    freopen("park.in","r",stdin);
    freopen("park.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;++i)
    scanf("%d",&a[i]);
    for(register int i=1;i<=n;++i)
    scanf("%d",&b[i]);
    for(register int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&l,&r,&k);
        register int tp=k;
        ans=0;
        for(register int j=l;j<=r;++j)
        {
            tp+=a[j];
            tp=minn(tp,b[j]);
            ans=maxx(ans,tp);
            tp=maxx(tp,k);
        }
        printf("%d\n",ans);
    }
}