# 52 E. Domino Principle （dp）

# 52 E. Domino Principle （dp）

题目链接：

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

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

AC代码：

#includeusing 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>a[i].x>>a[i].h; a[i].id=i; } sort(a,a+n,cmp); for(int i=0;i=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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。