# 52 E. Domino Principle （dp）

我就是我 2022-06-17 03:21 123阅读 0赞

题目链接：

[点击打开链接][Link 1]

http://codeforces.com/contest/56/problem/E

题意：

给你一些多米诺骨牌，在x轴上从左到右排列在一起，问，每一个倒向右边的时候会压倒多少个骨牌？给定的骨牌并不是按照x从小到大的顺序排列的。

题解：

假设第 i个骨牌要倒向右面，这时要考虑 i 之前的骨牌，考虑 i 之前某一个骨牌 j 倒下之后的最优值。

如果 i 倒下后压倒 j，那 i 的最优值需要加上 j 的最优值。状态转移一下就可以了。

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=100010;
    int n;
    struct node
    {
    	int x,h;
    	int dp,id;
    }a[maxn];
    int sum[maxn];
    bool cmp(node a,node b)
    {
    	return a.x>b.x;
    }
    
    int main()
    {
       //freopen("in.txt","r",stdin);
    	cin>>n;
    	for(int i=0;i<n;i++)
    	{
    		cin>>a[i].x>>a[i].h;
    		a[i].id=i;
    	}
    	sort(a,a+n,cmp);
    	for(int i=0;i<n;i++)a[i].dp=1;
    	sum[a[0].id]=1;
    	for(int i=0;i<n;i++){
    		for(int j=i-1;j>=0;j-=a[j].dp)
    		{
    			if(a[j].x+1>a[i].x+a[i].h) break;//后面的不能被前面的压倒
    			else a[i].dp += a[j].dp; 
    		 
    		}
    		sum[a[i].id]=a[i].dp; //状态转移 
    	//	printf("%d %d\n",a[i].id,a[i].dp);
    	}
    	for(int i=0;i<n;i++){
    		printf("%d ",sum[i]); 
    	}
    	return 0;
    }

[Link 1]: http://codeforces.com/contest/56/problem/E

发表评论取消回复

表情：

评论列表（有 0 条评论，123人围观）

还没有评论，来说两句吧...

相关阅读

相关【DP】CF598E

[Problem - E - Codeforces][] ![ea06301014c348d39e3a5f448de96951.png][] Code： incl

深碍√TFBOYSˉ_/ 2024年03月22日 22:01/ 0 赞/ 96 阅读

相关【DP+博弈】ABC195 E

[E - Lucky 7 Battle (atcoder.jp)][E - Lucky 7 Battle _atcoder.jp] 题意： ![44faf1c04ab542

ゞ浴缸里的玫瑰/ 2024年03月17日 15:40/ 0 赞/ 50 阅读

相关【DP】CF Edu 21 E

[Problem - E - Codeforces][] 题意： ![c96fb68444bf465d95ac7bb92caf33cf.png][]![b7481c00b1

骑猪看日落/ 2024年03月09日 00:41/ 0 赞/ 93 阅读

相关 Codeforces 750E 线段树DP

题意：给你一个字符串，有两种操作：1：把某个位置的字符改变。2：询问l到r的子串最少需要删除多少个字符，使得这个子串含有2017子序列，并且没有2016子序列？思路：线段树

布满荆棘的人生/ 2023年08月17日 17:22/ 0 赞/ 101 阅读

相关 Codeforces 735E 树形DP

题意：给你一棵树，你需要在这棵树上选择一些点染成黑色，要求染色之后树中任意节点到离它最近的黑色节点的距离不超过m，问满足这种条件的染色方案有多少种？思路：设dp\[x\]\

灰太狼/ 2023年08月17日 17:22/ 0 赞/ 132 阅读

相关 Codeforces 722E 组合数学 DP

题意：有一个n \ m的棋盘，你初始在点(1, 1)，你需要去点(n, m)。你初始有s分，在这个棋盘上有k个点，经过一次这个点分数就会变为s / 2(向上取整），问从起点到终

冷不防/ 2023年08月17日 17:22/ 0 赞/ 139 阅读

相关 ZOJ Problem Set - 2563 Long Dominoes 【状压dp】

题目：[ZOJ Problem Set - 2563 Long Dominoes][] 题意：给出1\3的小矩形，求覆盖m\n的矩阵的最多的不同的方法数？

朱雀/ 2022年08月13日 00:53/ 0 赞/ 17 阅读

相关 # 52 E. Domino Principle （dp）

题目链接： [点击打开链接][Link 1] http://codeforces.com/contest/56/problem/E 题意：给你一些多米诺骨

我就是我/ 2022年06月17日 03:21/ 0 赞/ 124 阅读

相关 Nokia E52使用技巧集锦

Nokia E52使用技巧集锦 1.在待机锁健的情况下，按方向键中间的确认键，屏幕会显示大字体时间/日期/待机模式，松开就推出，要长时间显示就长按。加注：按四向方

我就是我/ 2022年05月16日 08:13/ 0 赞/ 237 阅读

相关 E - Pearls（dp）

题目描述： In Pearlania everybody is fond of pearls. One company, called The Royal Pearl,

╰+哭是因爲堅強的太久メ/ 2022年04月24日 00:46/ 0 赞/ 139 阅读