精华内容
下载资源
问答
  • 区间Dp
    2018-04-14 13:23:00

    所谓区间dp,顾名思义就是在一段区间上的动态规划。它既要满足dp问题的最优子结构和无后效性外,还应该符合在区间上操作的特点。我的理解是往往会对区间进行合并操作。抑或是单个元素(可看成一个小区间)跨区间进行操作。例如括号匹配问题,石子合并问题(通过多次的相邻合并,最后实质上会产生跨区间的合并,如果你把其中的石子看作参考系的话就很容易感觉出来),还有在整数中插入运算符号的问题(利用运算符的优先级以及交换律可看出)

    这样以来,如果我们要得知一个大区间的情况,由于它必定是由从多个长度不一的小区间转移而来(转移情况未知),我们可以通过求得多个小区间的情况,从而合并信息,得到大区间。

    对于一个长度为n的区间,确定它的子区间需要首尾两个指针,显然子区间数量级为n2,那区间dp的复杂度也就为n2

    递推式一般由小区间推到大区间,所以第一层循环一般是区间长度,第二层循环是区间起点。

    1 for(int len = 1; len < m; len++)//区间长度
    2 {
    3     for(int start = 0; start + len < m; start++)//区间起点
    4     {
    5         int end = start + len;//区间终点
    6         //递推式......   
    7     }
    8 }   

     

    转载于:https://www.cnblogs.com/fzl194/p/8831316.html

    更多相关内容
  • 区间dp

    2017-10-28 21:03:48
    大致分成两种,小区间推大区间,大区间推小区间一些平常的区间dp只要定义dp[][]两维就行,两种不同的定义方式。一种dp[i][j] 表示左端为i右端为j。另一种是dp[i][j] 表示左端为i,长度为j。两种写法对应的循环也不同...

    区间dp写起来就比概率dp写起来有套路多了。
    总的来说,自认为区间dp就只有三四种套路。

    大致分成两种,小区间推大区间,大区间推小区间

    一些平常的区间dp只要定义dp[][]两维就行,两种不同的定义方式。一种dp[i][j] 表示左端为i右端为j。另一种是dp[i][j] 表示左端为i,长度为j。两种写法对应的循环也不同。

    以小区间为例
    对于第一种,dp[i][j] 左端点+右端点

    for(int i=n;i>=1;i--)
        for(int j=i;j<=n;j++)

    一般第一重循环表示右端点,第二重循环表示左端点。这样写是当要求的答案是dp[1][n] 的时候。
    对于第二种,dp[i][j] 左端点+长度

    for(int i=1;i<=n;i++)
        for(int j=1;i+j<=n;j++)
            ……

    一般第一重循环表示长度,第二重循环表示左端点。

    还有些题目就不能直接这样写了,可能区间dp没那么明显,区间性不高。可以根据一些性质转化成区间dp。

    以下是例题分析:(有题不是区间dp)

    一、HDU 3280 Equal Sum Partitions
    第一题就不是区间dp……区间dp第一题不是区间dp,亏我想了这么久……暴力枚举和,然后判断一下,玄学就过了。

    二、HDU 4283 You Are the One
    比较明显的区间dp。开始时想把一个点往相邻的区间的头尾放,然后转移就行了。然后带了一组数据发现完全错。然后发现作为一个栈,为什么只能往头尾放?栈是先进后出,那么一个点进去后,可以晚点出来。那么对于一个点,就可以插入到后面区间任意一个位置。那么转移就简单了。套用第一个模板

    for(int l=1;l<=n;l++)
        for(int i=1;i+l<=n;i++){
            int j=i+l;
            dp[i][j]=1e9;
            for(int k=1;i+k-1<=j;k++)
                dp[i][j]=min(dp[i][j],dp[i+1][i+k-1]+dp[i+k][j]+k*(cnt[j]-cnt[i+k-1])+A[i]*(k-1));//cnt是前缀和
        }

    三、HDU 4293 Groups
    这道题如果直接去想区间dp,肯定会被他的分组弄糊。反方向想,如果一个人说他前面有a个人,后面b个人,那么如果想要这个人说真话,那么他肯定要站在[a+1,n-b]这个区间内。这个显然,那么这样就划分出区间来了。可以知道对于一个区间[L,R],有很多人要站在里面,那么这个区间可能要满出来了,那就要判一下。读入的时候把这些区间求出来。问题就转化为多个有权值的区间,从中选出一些不重叠的区间使权值最大。这种问题dp只要一维就行了。

    //预处理部分
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(x+y<=n&&n-y-x>A[x+1][n-y])A[x+1][n-y]++;//存在区间&&区间人数足够 
    }
    
    //dp部分
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            dp[i]=max(dp[i],dp[j-1]+A[j][i]);

    四、HDU 4412 Sky Soldiers
    求期望的区间dp。可以说dp的转移不是很难,难在预处理那一段。dp[i][j] 表示前i个点建立j个大本营要的代价。此时转移还要一个数组cost[i][j] 来辅助,表示在[i,j]区间建一个大本营的代价。那么循环一个中间点,然后往上一层转移就行。

    for(int i=2;i<=n;i++)
        for(int j=1;j<=m;j++){
            dp[i][j]=1e9;
            for(int k=0;k<i;k++)dp[i][j]=min(dp[i][j],dp[k][j-1]+cost[k+1][i]);
            }

    主要是预处理cost这个数组。如果给了降落点的范围,那么就没有那么麻烦。但是题目没给范围,那就要离散了。离散用了map,还要用迭代器,麻烦。现在讲讲不用离散的。现在要往一个区间里放一个大本营,那么就要选一个最优的位置放大本营的位置,而[i,j]又要循环过去都求一遍,那么可以一边枚举左右端点,一边选出一个最优的大本营地址。我是从后往前算的。当区间右端点固定时,最短点不断延伸,那么大本营显然会向左移动,那么每次都只要往左移动,那么大概就是n^2了。但是因为还要加map,一下子不知道怎么去重,看了一下题解,发现可以直接装起来,然后再拎出来就行了。

    五、HDU 4597 Play Game
    这个和取数游戏是一样的。因为两个人都是最有策略,那么只要用当前的总和减去另一个人的最有策略就行。dp要定义四维,分别是两行的左右端点。这道题其实用记忆化搜索写起来更加方便易懂。

    六、HDU 4745 Two Rabbits
    先肯定要把环变成一条链,只要多存一组就行了。转化为线性后,题目就变成了在一条链上求一个最长的回文子序列,因为顺时针、逆时针一样。那么转移起来就很简单了。要么从旁边传递值,要么相等加2。求答案时要注意一点,两个人的起点可能从同一个点开始,那么此时的值就是在n-1的长度里的最值再加1。

    for(int i=2*n;i>=1;i--)
        for(int j=i+1;j<=2*n;j++){
            dp[i][j]=max(dp[i+1][j],dp[i][j-1]);//转移
            if(A[i]==A[j])dp[i][j]=max(dp[i][j],dp[i+1][j-1]+2);//相等
        }
    int ans=0;
    for(int i=1;i<=n;i++)ans=max(ans,max(dp[i][i+n-1],dp[i][i+n-2]+1));//长度为n但起点不同,长度为n-1单起点相同

    七、HDU 5115 Dire Wolf
    这道套一下模板,把一个区间按照一个点切开成两个区间,然后左边的加右边的再加一下附加攻击值就行。用第二个模板

    for(int i=n;i>=1;i--)
        for(int j=i;j<=n;j++){
            dp[i][j]=1e9;
            for(int k=i;k<=j;k++)//中间点切开
                dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+A[k]+B[i-1]+B[j+1]);
                }

    八、HDU 5273 Dylans loves sequence
    其实我一直不觉的只是一道区间dp。明明就是前缀和维护一下就行了……

    九、HDU 5396 Expression
    这个区间dp的大致想法和第七题狼那道是一样的。也是在一个区间内枚举一个点,通过这个点把整各区间分成三部分(左,此点,右),然后再累加计算就行了。我写的是记忆化搜索,因为转移的时候计算的东西很多。题目要求合并的顺序不同,尽管答案相同,也算不同方案。这样就要在存一个数组表示这一个区间的方案又是多少。然后怎么求和呢。一个点把区间分成左右两部分,左边区间的和为L,方案数为Lc,右边分别为R,Rc。那么对于左区间来说,右区间的方案数就是左区间算的次数,那么左边的和就是L* Rc。同理右边是R* Lc。累加起来就行(只限于加减,乘法只要L*R就行)。方案数要多求一个东西。Lc和Rc仅限于他们自己的区间,合并后可以左边一个右边一个,这也是不同的方案,虽然答案一样。那么还要乘一个C(l+r,l),l,r分别是左右区间的符号数。总方案数就按上面的方法变成了C(l+r,l) * Lc * Rc。
    代码可以上上度娘查,我的太丑了。

    十、HDU 5900 QSC and Master
    也是一个比较模板的题。用一个点去切一个区间。但是切的时候要注意,因为要使两个数可以合并,除了gcd>1,还要这两个数之间的数合并完了,这还要一个数组来记录这个。

    for(int i=n;i>=1;i--)
        for(int j=i+1;j<=n;j++){
            if(dp[i+1][j]>dp[i][j-1])dp[i][j]=dp[i+1][j];else dp[i][j]=dp[i][j-1];
            Q[i][j]=-1;
            for(int k=i+1;k<=j;k++)
                if(Q[i+1][k-1]!=-1&&gcd(A[i],A[k])>1){
                    dp[i][j]=max(dp[i][j],dp[i+1][k-1]+dp[k+1][j]+1LL*V[i]+1LL*V[k]);
                    Q[i][k]=1;
                    if(Q[k+1][j]!=-1){Q[i][j]=1;break;}
                }
        }

    我这个程序要卡常,因为gcd太慢了,如果把if语句里的gcd放在前面判断的话会T,如果先判断区间是否全部已经合并会快一些。

    十一、HDU 6103 Kirinriki
    这也不是区间dp。因为求的两个字符串可以看成是对称的,对称的就存在一个中间点,那么就枚举中间点。枚举中间点后,还要判断他们的值是否小于等于m。可以用尺取的方法。先把每一个对应的点求出来,然后尺取就行。中心点也分两种情况:一种是中心点是点,一种中心点不存在,但是是堆成的。贴其中一段的。

    for(int i=1;i<=n;i++){//中心点
        int len=min(i-1,n-i);//此中心点下最长的长度
        for(int j=1;j<=len;j++){
            dp[j]=abs(str[i-j]-str[j+i]);//对应的值
        }
        int l=1,r=1,t=dp[1];
        while(r<=len){//尺取
            while(l<=r&&t>m){
                t-=dp[l];
                l++;
            }
            if(ans<r-l+1)ans=r-l+1;
            r++;
            t+=dp[r];
        }

    十二、HDU 6212 Zuma
    写前要处理一下。给的是01串,我们不可能直接用01串来吧?颜色相同的几个球肯定是放在一起考虑的,那么就合并起来就行了。
    定义dp[i][j] 表示[i,j]区间打完要多少下。转移有三点,我只想到了两点,第三点真的想不到。
    第一点:把区间[L,R]分成[L,k]和[k+1,R]两块,然后把两块的直接加起来转移进来,这要枚举一个中间点
    第二点:当区间[L,R]的两端球的颜色相同时,把中间的球打掉,两边的球会往中间靠拢,当靠拢后的球大于等于三个时,直接转移,否则在往里面打一个球就行了(因为求的个数肯定大于等于1)
    第三点:当区间[L,R]的两端的球的颜色相同时,可以找一个颜色相同的中间点k且此点球只有一个,把[L+1,k-1]和[k+1,R-1]的区间打掉,然后合并。此情况两边的球要保证!(A[L]==2&&A[R]==2)。原因是如果左边的球有两个,右边的球有两个的话,一往中间合并就炸掉了。例如2+1+2,左边的2+1变3,右边的1+2变3,不管怎么样都不行。但是1+1+2行,因为可以先1+1变2再2+2变4.

    for(int i=n;i>=1;i--)
        for(int j=i;j<=n;j++){
            if(i==j){dp[i][j]=3-A[i];continue;}
            dp[i][j]=1e9;
            for(int k=i;k<j;k++)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);//第一种情况,[L,R]=[L,k]+[k+1,R]
            if((j-i)%2==1)continue;
            dp[i][j]=min(dp[i][j],dp[i+1][j-1]+(A[i]+A[j]==2));//第二种
            if(!(A[i]==2&&A[j]==2))//第三种
                for(int k=i+1;k<j;k++)
                    if(A[k]==1&&(k-i)%2==0&&(j-k)%2==0)dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k+1][j-1]);
        }

    总结一下:
    1、普通的区间dp都是很有套路的,模板就两个,按照自身习惯,再结合一下题意看写哪一个方便写哪一个。
    2、区间dp常见的转移方式有:

    1)两个区间合并成一个区间
    2)把一个点将一个区间切成两部分,然后再把两边的加起来
    3)在一个区间里枚举一个点,然后切成两部分

    3、把题目中的一些条件转换成范围性的东西,然后用区间dp
    4、其他:环变链:多一倍;字符串的回文或匹配:枚举中心点。

    展开全文
  • 所以我们需要反过来从大区间小区间推。 d p [ i ] [ j ] [ k ] dp[i][j][k] 表示左端点为 i i ,右端点为 j j ,如果 k = 0 k=0 则表示除了左端点都没有交现在在左端点,如果 k = 1 k=1 则表示除了右端点都没有交...

    Turning in Homework
    Time Limit: 1000MS Memory Limit: 30000K
    Total Submissions: 1172 Accepted: 519
    Description

    Bessie must turn in her homework for her C classes (1 <= C <= 1,000) at Moo U so that she still has time to chew the cud with her fellow classmates as they wait for the bus to go home.

    Teachers accept homework submissions only after they have finished their classes and also cleaned the chalkboard, put away lab supplies,and so on. The input data tells the earliest time a teacher will accept homework.

    Bessie starts at one end (distance 0) of a hallway H (1 <= H <= 1,000) meters long and walks at the rate of one meter per second to various classrooms (in any order she chooses) to turn in her homework. Each classroom is located along this hallway, as well as the door to the waiting area for the buses.

    Given the location of both the exit and the classrooms and also the teachers’ schedules, determine the earliest time that Bessie can exit the door to the waiting area for the buses. Bessie must turn in all her homework before exiting. The act of turning in the homework takes no time, by the way.
    Input

    • Line 1: Three integers: C, H, and B. B (0 <= B <= H) is the distance from the hall entrance to the bus waiting area.

    • Lines 2..C+1: Each line contains two integers that describe a classroom where homework is to be submitted. The first integer (0..H) is the number of meters to the classroom from the hallway entrance. The second integer (0..10,000) is the first time (in seconds) that the teacher for that course will accept homework.
      Output

    • Line 1: A single integer: the earliest second that Bessie can exit the door to the waiting area for the buses.
      Sample Input

    4 10 3
    8 9
    4 21
    3 16
    8 12
    Sample Output

    22
    Hint

    Time Action

    0 Bessie walks to the classrooms 8 meters down the hall (at 8m)

    8 Bessie waits 1 second

    9 Bessie turns in the first set of homework

    9 Bessie waits 3 seconds, thinking about cool hay in the summertime

    12 Bessie turns in the other homework for this location

    12 Bessie walks back to the classroom 4 meters down the hall (at 4m)

    16 Bessie waits 5 seconds, thinking of a handsome bull she once met

    21 Bessie turns in her homework

    21 Bessie walks back to the classroom 1 meters down the hall (at 3m)

    22 Bessie turns in her homework

    22 Bessie exits, since this also the location of the bus exit

    Thus, Bessie can leave at time 22. No better schedule exists.
    Source

    USACO 2004 U S Open

    题目大意

      数轴上有一些教室,知道每个教室的位置和开门时间,问从 x=0 的点到所有点交完作业后到达一个给定的终点的最小时间(每个教室只能在开门后才能交作业)。

    解题思路

      首先可以发现当区间 [i,j] 的作业都没有交的时候,先访问 i 或先访问j一定是最优的。
      由于最终还要走到一个给定的终点,所以如果按照正常的区间DP,从小区间往大区间推的话就不能考虑到最终位置到终点的距离。所以我们需要反过来从大区间往小区间推。 dp[i][j][k] 表示左端点为 i ,右端点为j,如果 k=0 则表示除了左端点都没有交现在在左端点,如果 k=1 则表示除了右端点都没有交现在在右端点。那么最终得到 dp[i][i][0]=dp[i][i][1] 就是交完作业到达 i 的最短时间,再分别加上到终点的距离找最小值即为答案。
      状态的转移就是利用贪心仅在区间的端点转移。总时间复杂度O(N2)

    AC代码

    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <stack>
    #include <cmath>
    #include <cstdlib>
    #include <string>
    #include <map>
    using namespace std;
    #define INF 0x3f3f3f3f
    #define LL long long
    #define fi first
    #define se second
    #define mem(a,b) memset((a),(b),sizeof(a))
    #define sqr(x) ((x)*(x))
    
    const int MAXN=1000+3;
    int N, L, T;
    pair<int, int> p[MAXN];//位置,解锁时间
    int dp[MAXN][MAXN][2];//表示i到j之间除了(k?j:i)都没有交的最小花费
    
    void init()
    {
        mem(dp, 0x3f);
    }
    
    int main()
    {
        scanf("%d%d%d", &N, &L, &T);
        init();
        for(int i=1;i<=N;++i)
            scanf("%d%d", &p[i].fi, &p[i].se);
        sort(p+1, p+1+N);
        dp[1][N][0]=max(p[1].fi, p[1].se);
        dp[1][N][1]=max(p[N].fi, p[N].se);
        for(int len=N-1;len>0;--len)
        {
            for(int l=1;l+len-1<=N;++l)
            {
                int r=l+len-1;
                if(l>1)
                {
                    dp[l][r][0]=min(dp[l][r][0], dp[l-1][r][0]+p[l].fi-p[l-1].fi);
                    dp[l][r][1]=min(dp[l][r][1], dp[l-1][r][0]+p[r].fi-p[l-1].fi);
                }
                if(r<N)
                {
                    dp[l][r][0]=min(dp[l][r][0], dp[l][r+1][1]+p[r+1].fi-p[l].fi);
                    dp[l][r][1]=min(dp[l][r][1], dp[l][r+1][1]+p[r+1].fi-p[r].fi);
                }
                //如果需要等待则等待
                dp[l][r][0]=max(dp[l][r][0], p[l].se);
                dp[l][r][1]=max(dp[l][r][1], p[r].se);
            }
        }
        int ans=INF;
        for(int i=1;i<=N;++i)
            ans=min(ans, dp[i][i][0]+abs(T-p[i].fi));//加上每个位置到终点的距离更新答案
        printf("%d\n", ans);
    
        return 0;
    }
    展开全文
  • 区间贪心

    2019-02-17 10:08:07
    我们会发现,当区间相交时,我们用小区间就行了,能保证我们找出的不相交的区间最多。 然后我们将所有区间的左端点也就是 x 从到小排序,然后每次找出右端点在这个左端点左面的就是一个,然后...

    题目描述

    给出N个开区间(x,y),从中选择尽可能多的开区间,使得这些区间两两没有交集。

    看到这一个题我们需要现在纸上画一画,有3种情况

    1) 区间相交。2)区间不相交。3)区间包含(其实也算区间相交)。

    我们会发现,当区间相交时,我们用小区间就行了,能保证我们找出的不相交的区间最多。

    然后我们将所有区间的左端点也就是 x 从大到小排序,然后每次找出右端点在这个左端点左面的就是一个,然后选取这个区间的左端点作为下次判断的标准,当左端点相同时,按照右端点 y 从小到大排序,就是我们检查时先检查(左端点相同时)右端点小的(正好可以去去除区间包含的大区间)。

    这就是整体思路了,我们就要看代码了。

    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<math.h> 
    #include<stdio.h>
    using namespace std;
    const int maxn = 105;
    class Inteval{
    	public:
    		int x, y;
    }I[maxn];
    bool cmp(Inteval a, Inteval b){
    	if(a.x != b.x)
    		return a.x > b.x;	//左端点不同的,从大到小排序 
    	else
    		return a.y < b.y;	//左端点相同的,从小到大排序 
    }
    int main(){
    	int n;
    	while(scanf("%d", &n), n != 0){
    		for(int i = 0; i < n; i++){
    			scanf("%d%d", &I[i].x, &I[i].y);
    		}
    	
    		sort(I, I + n, cmp);
    		int ans = 1;	//至少就有一个区间。 
    		int LastX = I[0].x;
    		for(int i = 1; i < n; i++){
    			if(I[i].y <= LastX){	//思考何时加= 何时不加= 
    				LastX = I[i].x;
    				ans++;
    			}
    		} 
    		printf("%d\n", ans); 
    	}
    	return 0;
    } 

    然后反向一波 ,如果我们是以右端点作为端点,我们应怎么写这个代码

    思路,我们如果用右端点y,那么我们排序是右端点y 从小到大的顺序排序的,如果右端点相同的话,我们选择左端点大的,我们先以第一个作为基础,然后遍历,找到第一左端点在右端点右边的 ans++ ,然后以这个区间的右端点作为基础继续比较。

    代码如下

    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #include<math.h> 
    #include<stdio.h>
    using namespace std;
    const int maxn = 105;
    class Inteval{
    	public:
    		int x, y;
    }I[maxn];
    bool cmp(Inteval a, Inteval b){
    	if(a.y != b.y)
    		return a.y < b.y;	//右端点不同的,从小到大排序 
    	else
    		return a.x > b.x;	//右端点相同的,从大到小排序 
    }
    int main(){
    	int n;
    	while(scanf("%d", &n), n != 0){
    		for(int i = 0; i < n; i++){
    			scanf("%d%d", &I[i].x, &I[i].y);
    		}
    	
    		sort(I, I + n, cmp);
    		int ans = 1;	//至少就有一个区间。 
    		int LastY = I[0].y;
    		for(int i = 1; i < n; i++){
    			if(I[i].x >= LastY){	 
    				LastY = I[i].y;
    				ans++;
    			}
    		} 
    		printf("%d\n", ans); 
    	}
    	return 0;
    } 

    第2种思路

    1)按照左端点(开始时间升序排序)。

    2)然后开始遍历所有区间,(1)先看下个区间的左端点是否在当前区间右端点的右边,如果在右边,ans++,(2)如果在右边(下个区间的左端点在这个区间内),并且当前选择选择区间的右端点大于下个区间的右端点那就换区间进行比较,答案不+1,(就是区间包含的情况)

    /*区间贪心*/
    #include<iostream>
    #include<cstring>
    #include<math.h>
    #include<stdio.h>
    #include<algorithm>
    #include<queue>
    using namespace std;
    const int maxn = 120;
    struct type {
    	int x, y;
    };
    type I[maxn];
    bool cmp(type a, type b) {
    	if (a.x != b.x) return a.x < b.x;
    	else return a.y < b.y; 
    }
    int main() {
    	int n;
    	while(scanf("%d", &n), n != 0) {
    		for (int i = 0; i < n; ++i) {
    			scanf("%d%d", &I[i].x, &I[i].y);
    		}
    		sort(I, I + n, cmp);
    		int ans = 1, lastX = I[0].x, lastY = I[0].y;
    		
    		for(int i = 1; i < n; ++i) {
    			if(lastY <= I[i].x) {
    				ans ++;
    				lastX = I[i].x;
    				lastY = I[i].y;
    			} else {
    				if (lastY > I[i].y) {
    					lastX = I[i].x;
    					lastY = I[i].y;
    				}
    			}
    		}
    		printf("%d\n", ans);
    	}
    	return 0;
    } 

    然后我们延伸一下

    出个变形题,同学们注意,老师要变形了。

    区间选点问题:给出N个闭区间 [ x, y ], 求至少需要多少个点才能使每个闭区间中至少存在一个点。

    看题先干什么???

    对了,画图,我们先来动动手,咦,好像给上面的有一定的相似之处,然后我们一跺脚。深吸一口气,这智障的题,

    1)区间相交,2)区间不相交。

    不就这两种情况么,如果相交那就一个点,不相交则最少2个点嘛,就这么简单???

    那代码我们怎么写呢?,不还是判断有多少个不相交的区间么,这也太简单了把,然后经过一系列分析发现这个不是闭区间  我们只需要将

    I[i].y <= LastX //等号去掉不就行了么
    I[i].y < LastX

    这就很简单了,那我们总结下,

    看到区间比大小,我们第一个应该想起这个题,应该就是这个题的本质,根据端点去判断,这就是区间题的突破口

    然后总结一下贪心

    贪心是用来解决一类最优化问题,一般就是问最多,最少,最大值,最小值,最短,最长,只要这个题考最。。。。或者问怎么才能使。。。。。我们就可以考虑贪心算法。

    局部最优策略来推得全局最优结果的算法思想

    贪心算法适用的问题一定满足最优子结构。

    展开全文
  • 写在前边 我们有这么一个需求,老板和我们说,要求我们做这么一个员工...别着急,还有一个需求就是公司每个月都会进行抽奖福利,抽奖的方式是,老板随机抽取贡献值为第 K 的贡献值的员工送出福利一份,共选取 n ...
  • 区间dp总结

    2019-09-23 10:57:32
    最经典的一个区间dp问题是矩阵链乘问题,算导和一些算法书上都有介绍, ...第一次见这个问题是cj同学随手拍给我的一道题,当时就感觉像以前写过的一道区间dp,然后纸上了半天最后成功过了样例! 我们把...
  • 在一开始区间的dp值要初始化为正无穷(取一个很的值即可) 转移方程为dp[l][r] = min(dp[l][r], dp[l][j] + dp[j][r] + cost[l][j] + cost[j][r]) 我们每次从中一个多变形中找到一个分隔点,那么三角形划分时就...
  • 区间DP&树形DP

    2019-08-05 19:46:28
    区间DP 树形DP 例题 A:POJ-2955 Brackets B:UVA-10003 Cutting Sticks C:POJ-1651 Multiplication Puzzle D:HDU-3506 Monkey Party E:POJ-2342 Anniversary party F:HDU-1054 Strategic Game G:ZOJ-3201 T....
  • 区间DP

    千次阅读 2018-08-17 17:23:32
    区间DP 【个人理解】 我觉得所有的DP都是优化的枚举(可能学的少,至少线性DP我觉得是),把一开始的状态结果保存到到数组中,然后推导后面的状态。我觉得区间DP同理,也是一个由短区间推导长区间的一个过程。最...
  • 更新区间,更新的过程不是一直更新到最底层的结点,建树建好之后,每一个结点对应一个区间[l,r],需要更新的区间[L,R],把需要更新的区间划分成若干个小区间(可能是一个,可能是很多个),直到每一个子区间在树里面...
  • 碎碎念 这道题着实想了好久啊,自己做是不行了。看了大神的题解,就没有详细解释...石子合并那种题,就是最最模板的那种 :一次决策后就可以将一个大区间分成两个小区间,先解决小区间的问题再把小区间合并 对于这...
  • 区间dp——小结

    2018-01-20 19:36:08
    定义:区间dp,就是先求小区间的最优解,然后逐步合并到大区间的最优解 二.代码实现大致步骤: ①找状态转移方程。f[i][j]一般是表示i~j区间的数字相加的最小代价。每次用变量k将其分成(i~k和k+1~j)两段 ②区间...
  • ASimple Problem with Integers(POJ-3468)线段树 区间更新加区间求和题目大意 POJ-3468的原题链接 题目大意 有一个数组长度为N的数组,总共输入T组数据指令,当输入 Q 指令时,代表要将 下标在 a,b之间的元素...
  • 所谓区间dp,就是在一个区间上进行的dp, 一般通过将大区分割成小区间进行dp。 区间型动态规划,又称为合并类动态规划,是线性动态规划的扩展,它在分阶段地划分问题时,与阶段中元素出现的顺序和由前一阶段的区间...
  • 区间dp专题解题报告

    2019-03-27 16:21:30
    考虑分治的方法,大区间的解依赖于小区间的解,当得到小区间的解后就 可以合并小区间的解进而得到大区间的解。 注意:题目中所说的相邻的颜色不同,但是相邻的可以都是黑色。 */ POJ - 1651  好像是之前省赛...
  • 二重dp,区间dp

    2019-04-02 13:09:35
    决策区间由一个大区间分成几个小区间,通常套路是三个循环,第一个循环是区间长度,第二个循环是起始点的位置,第三个循环是那个变量j, 矩阵最优连乘 前提:一个n乘m的矩阵成一个m乘p的矩阵的运算量为...
  • 数据结构—八排序

    万次阅读 多人点赞 2021-12-13 13:19:54
    一、直接插入排序 void InsertSort(int* a, int n) { assert(a);... //将x插入到[0,end]的有序区间 while (end >= 0) { if (a[end] > x) { a[end + 1] = a[end]; //往后挪动一位
  • 挖坑法: 前后指针法: 快排的时间复杂度: 小区间优化: 承接上文:7排序算法-- 直接插入,希尔,冒泡,选择 --精解_luck++的博客-CSDN博客 堆排序: 关于堆排序的讲解 大家可以看一下我的这篇文章:【数据结构...
  • title: 「kuangbin带你飞」专题二十二 区间DP author: "luowentaoaa" catalog: true tags: - kuangbin - 区间DP - 动态规划 传送门 B.LightOJ - 1422 Halloween Costumes 题意 按顺序参加舞会,参加一个舞会要穿一...
  • 随便把你放在一个角落,你都能慢慢摸索出来,本质上就是你脑中已经对小区周边形成了整体图,并对关键节点了然于胸。把你放到陌生的小区,你可能就懵逼了,关键节点、整体图均没有,胡乱摸索,即便你把摸索路上所...
  • 全文超过26000字,建议收藏下来,以便后期翻阅学习,在讲解完什么是DP,附上了8道典型DP例题,覆盖了线性、区间、二维、四维等模型,最后简单说了下如何优化DP,虽然说不敢保证你把这8题弄懂后以后就能够在DP的题目...
  • ①单趟的实现(将x插入到 [0,end] 的有序区间) 即一般情况下的插入,我们随机列举了一些数字,待插入的数字分为两种情况 (1)待插入的数字是在前面有序数字的中间数,直接比较将x赋值给end+1位置
  • 区间dp笔记√

    2016-08-16 17:32:00
    区间DP是一类在区间上进行dp的最优问题,一般是根据问题设出一个表示状态的dp,可以是二维的也可以是三维的,一般情况下为二维。 然后将问题划分成两个子问题,也就是一段区间分成左右两个区间,然后将左右两个区间...
  • 最近已经好几天没更博客了,希望刘老师不要揍我(如果一定要揍的请让岳老师揍应该下手会轻点) 最近这几天学的是DP(简直吓人woc) 相信有一些小伙伴会和我一样一脸懵逼 所以我决定,以一个菜逼的视角来总结...
  • 主要步骤(2)堆和小堆(3)父子结点(3)主要步骤(4)向下调整法(5)特别注意(6)代码实现(7)性能分析三,交换排序1,冒泡排序(1)基本思想(2)主要步骤(3)代码实现(4)冒泡和直接插入相比较(5)性能...
  • 冒泡排序 在同一个数组中,从数组第一个数开始,相邻两个数进行比较,按照小左右或者右小左的顺序,依次循环遍历,进行排序!
  • 4.排升序建堆还是建小堆? 三.交换排序(一).冒泡排序 4.冒泡与直接插入排序相 (二).快速排序 1.挖坑法 2.左右指针法 3.前后指针法 四.归并排序 (一).归并排序 1.思路: 2.代码: 3.对文件中的数据排序: ...
  • i 这样写思路比较清晰,但是回溯的部分卡到我了,因为我这样写在dfs到障碍后才让障碍消失,后面回溯起来就需要放在dfs的外面而不是里面,如果在里面的意思就是一个方向结束了就把障碍回溯,实际上应该是几个方向都...
  •  在这里起点要从s-1到1倒着是为了保证先确定小区间的最优值再扩展到大区上~~别忘了;    2.经典的线式环境下的区间dp  (1).sdnu 1045 http://www.acmicpc.sdnu.edu.cn/problem/show/1045(附帐号 heheda11...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 528
精华内容 211
关键字:

小区间推大区间的话

友情链接: 21295998.zip