首页 > 其他分享 >洛谷题单指南-分治与倍增-P6648 [CCC2019] Triangle: The Data Structure

洛谷题单指南-分治与倍增-P6648 [CCC2019] Triangle: The Data Structure

时间:2024-09-30 14:50:17浏览次数:10  
标签:Triangle int 洛谷题 最大值 long st len P6648 三角形

原题链接:https://www.luogu.com.cn/problem/P6648

题意解读:在一个n行的数字三角形中,求所有边长为k的正三角形最大值之和。

解题思路:

1、枚举法

枚举每一个边长为k的三角形,在其中求max,然后累加,n最多3000,时间复杂度是n^4,显然超时。

2、倍增和ST思想

此题非常类似于RMQ问题,也就是求区间最值,只不过区间是一个三角形

可否借助ST思想?

不妨设st[i][j][k]表示从(i,j)开始,大小为2^k的三角形内最大值,a[i][j]表示三角形(i,j)位置的值

初始化:st[i][j][0] = a[i][j]

递推:

求值:

假设要计算(i,j)为顶点,边长为k的三角形内最大值

想到这里,兴匆匆的写出如下代码:

0分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 3005;
int a[N][N];
int st[N][N][12]; //st[i][j][k]表示从(i,j)开始,大小为2^k的三角形内最大值
int n, k;
long long ans;

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            cin >> a[i][j];
            st[i][j][0] = a[i][j];
        }
    }

    for(int l = 1; l < log2(n); l++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                st[i][j][l] = st[i][j][l - 1];
                int x = i + (1 << l - 1);
                for(int y = j; y <= j + (1 << l - 1); y++)
                {
                    st[i][j][l] = max(st[i][j][l], st[x][y][l - 1]);
                }
            }
        }
    }

    for(int i = 1; i + k - 1 <= n; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            int len = log2(k);
            int maxijk = st[i][j][len];
            int x = i + k - (1 << len);
            for(int y = j; y <= j + k - (1 << len); y++)
            {
                maxijk = max(maxijk, st[x][y][len]);
            }
            ans += maxijk;
        }
    }
    cout << ans;

    return 0;
}

原来是int st[N][N][12]爆内存了,需要进一步优化,递推式中l只依赖l-1,因此可以用滚动数组进行优化,于是有:

25分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 3005;
int a[N][N];
int st[N][N][2]; //st[i][j][k]表示从(i,j)开始,大小为2^k的三角形内最大值,第三维用滚动数组优化
int n, k;
long long ans;

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            cin >> a[i][j];
            st[i][j][0] = a[i][j];
        }
    }

    for(int l = 1; l <= log2(k); l++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                st[i][j][l % 2] = st[i][j][(l - 1) % 2];
                int x = i + (1 << l - 1);
                for(int y = j; y <= j + (1 << l - 1); y++)
                {
                    st[i][j][l % 2] = max(st[i][j][l % 2], st[x][y][(l - 1) % 2]);
                }
            }
        }
    }

    for(int i = 1; i + k - 1 <= n; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            int len = log2(k);
            int maxijk = st[i][j][len % 2];
            int x = i + k - (1 << len);
            for(int y = j; y <= j + k - (1 << len); y++)
            {
                maxijk = max(maxijk, st[x][y][len % 2]);
            }
            ans += maxijk;
        }
    }
    cout << ans;

    return 0;
}

究其原因,关键代码的时间复杂度是logk*N^3,需要进一步优化时间

观察代码:

红色框中是要计算从j开始,窗口长度(1<<l-1)+ 1的最大值,显然可以用单调队列优化,于是就有了以下最终版代码:

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 3005;
int a[N][N];
int st[N][N][2]; //st[i][j][k]表示从(i,j)开始,大小为2^k的三角形内最大值,第三维用滚动数组优化
int n, k;
long long ans;
int q[N], head, tail;

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            cin >> a[i][j];
            st[i][j][0] = a[i][j];
        }
    }

    for(int l = 1; l <= log2(k); l++)
    {
        for(int i = 1; i <= n; i++)
        {
            head = 1, tail = 0; //单调队列头、尾指针初始化
            int len = (1 << l - 1) + 1; //窗口大小
            int x = i + (1 << l - 1); //起始横坐标
            for(int j = 1; j <= n; j++)
            {
                st[i][j][l % 2] = st[i][j][(l - 1) % 2];
                //去头
                while(head <= tail && j - q[head] + 1 > len) head++;
                //去尾
                while(head <= tail && st[x][j][(l - 1) % 2] > st[x][q[tail]][(l - 1) % 2]) tail--;
                //存入
                q[++tail] = j;   
                //取窗口最大值,并与i,j - len + 1位置对应的值取max
                if(j >= len)
                    st[i][j - len + 1][l % 2] = max(st[i][j - len + 1][l % 2], st[x][q[head]][(l - 1) % 2]);
            }
        }
    }

    for(int i = 1; i + k - 1 <= n; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            int len = log2(k);
            int maxijk = st[i][j][len % 2];
            int x = i + k - (1 << len);
            for(int y = j; y <= j + k - (1 << len); y++)
            {
                maxijk = max(maxijk, st[x][y][len % 2]);
            }
            ans += maxijk;
        }
    }
    cout << ans;

    return 0;
}

 

标签:Triangle,int,洛谷题,最大值,long,st,len,P6648,三角形
From: https://www.cnblogs.com/jcwy/p/18441842

相关文章

  • 洛谷题单指南-分治与倍增-P4155 [SCOI2015] 国旗计划
    原题链接:https://www.luogu.com.cn/problem/P4155题意解读:在m个点的环上,有n个区间,且各个区间之间没有包含关系,计算从每个区间开始,最少要多少个区间能覆盖环上所有m个点。解题思路:本质上是一个区间覆盖问题!1、破环成链由于题目中是一个环,对于环的问题,在区间DP中介绍过,经典处理......
  • 洛谷题单指南-分治与倍增-P3517 [POI2011] WYK-Plot
    原题链接:https://www.luogu.com.cn/problem/P3517题意解读:有n个连续的点p1,p2,...,pn,将这n个点分成不超过m堆,每堆点连续,每一堆都缩成一个点qi,要使得原来的点p1~ps距离qi的最大值最小(最相似),求这个相似度,并计算一共分成几堆,以及每堆缩到的点qi的坐标。解题思路:要使得若干点缩到一......
  • 洛谷题单指南-分治与倍增-P3509 [POI2010] ZAB-Frog
    原题链接:https://www.luogu.com.cn/problem/P3509题意解读:n个点,每个点上有一只青蛙每次跳到距离自己第k近的点,m次之后跳到哪个点。解题思路:1、计算距离每个点第k近的点,存入ne[N]给定一个点i,距离i第k近的点一定在长度为k+1个点的窗口内,窗口包括i并且,第k近的点只能是左端点或者......
  • 洛谷题单指南-分治与倍增-P2345 [USACO04OPEN] MooFest G
    原题链接:https://www.luogu.com.cn/problem/P2345题意解读:有n头牛,每头牛都有听力v、坐标x两个属性,要计算每两头牛的max{vi​,vj​}×∣xi​−xj​∣之和。解题思路:首先想到的肯定是枚举法,需要O(n^2)的复杂度有没有优化的方法?可以采用分治法!由于是计算两头牛之间的max{vi​,......
  • 【洛谷 P1216】[USACO1.5] [IOI1994]数字三角形 Number Triangles 题解(动态规划)
    [USACO1.5][IOI1994]数字三角形NumberTriangles题目描述观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。在上面的样例中,从的路径产生了最大权值。输入格式第一个行一个正整数......
  • 洛谷题单指南-分治与倍增-P2415 集合求和
    原题链接:https://www.luogu.com.cn/problem/P2415题意解读:计算集合所有子集中元素之和。解题思路:集合的特性:互异性,元素各不相同来看样例:23,可以组成的子集有空23232和3都出现2次再比如:123,可以组成的子集有空12312 13231231,2,3各出现4次由于在集合中......
  • 洛谷题单指南-分治与倍增-P7167 [eJOI2020 Day1] Fountain
    原题链接:https://www.luogu.com.cn/problem/P7167题意解读:从喷泉任意一个圆盘倒水,水流经的圆盘直径必须递增,水最后流到哪个圆盘。解题思路:1、枚举法有30%的数据范围在N<=1000,Q<=1000,因此枚举也可以得到30分。可以通过单调栈预计算每个圆盘后面第一个直径更大的圆盘位置Next[......
  • 洛谷题单指南-分治与倍增-P1226 【模板】快速幂
    原题链接:https://www.luogu.com.cn/problem/P1226题意解读:快速幂模版题。解题思路:1、分治法要计算a^b,可以对b分情况讨论:如果b是偶数,即b=2t,a^b=a^t*a^t如果b是奇数,即b=2t+1,a^b=a*a^t*a^t很容易用递归实现100分代码:#include<bits/stdc++.h>usingnamespa......
  • 洛谷题单指南-分治与倍增-P1966 [NOIP2013 提高组] 火柴排队
    原题链接:https://www.luogu.com.cn/problem/P1966题意解读:计算两个序列∑(ai​−bi​)^2的最小值,对10^8-3取模。解题思路:1、贪心思路要使得两个序列对应位置元素之差的平方和最小,必须满足两个序列相对排序是一致的,什么意思?设a序列有两个元素:a1,a2,b序列有两个元素b1,b2当a1<a2,b......
  • 洛谷题单指南-分治与倍增-P1908 逆序对
    原题链接:https://www.luogu.com.cn/problem/P1908题意解读:求序列逆序对数。解题思路:1、暴力法对于每一个数,寻找后面有多少数比其小,或者采用冒泡排序,交换的次数即逆序对的个数,复杂度为O(n^2)2、归并排序法在归并排序过程中,会进行有序序列的合并,设两部分连续的有序序列为a[s1,......