生活随笔
收集整理的這篇文章主要介紹了
CF56E Domino Principle 树状数组 + 简单dp
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
一個比較簡單的題，但是我還是沒做出來(哭。
很容易想到從后往前做，所以我們可以維護一個dp數組f，f(i)表示到第i個牌倒下能達到的最遠距離。
f直接倒著跑，每次取[x,x+h?1][x,x+h-1][x,x+h?1]的最大值即可，可以用線段樹比較容易的解決問題。但是看到一個大神直接把f初始值設為**-INF** ，因為是從后往前跑的，所以前面的一直都是**-INF**，所以可以直接用樹狀數組維護前綴最大值，單點修改即可。
代碼寫的賊麻煩，離散化的時候完全不需要 x+h-1 的點進行離散化，這樣可以直接查找x是第幾個，不需要跟我一樣多寫一個樹狀數組。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
#define lowbit(x) ((x)&(-x))
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
,se
;
int ans
[N
],tr
[N
],trr
[N
];
int f
[N
];
vector
<int>v
;
struct Node
{int x
,h
,id
;
}p
[N
];int find(int x
)
{return lower_bound(v
.begin(),v
.end(),x
)-v
.begin();
}bool cmp(Node a
,Node b
)
{return a
.x
>b
.x
;
}void mf(int x
,int c
)
{for(int i
=x
;i
<=se
;i
+=lowbit(i
)) tr
[i
]=max(tr
[i
],c
);
}int ask(int x
)
{int ans
=-INF
;for(int i
=x
;i
;i
-=lowbit(i
)) ans
=max(ans
,tr
[i
]);return ans
;
}void add(int x
)
{for(int i
=x
;i
<=se
;i
+=lowbit(i
)) trr
[i
]+=1;
}int sum(int x
)
{int ans
=0;for(int i
=x
;i
;i
-=lowbit(i
)) ans
+=trr
[i
];return ans
;
}int main()
{
scanf("%d",&n
); memset(tr
,-0x3f,sizeof(tr
));for(int i
=1;i
<=n
;i
++) scanf("%d%d",&p
[i
].x
,&p
[i
].h
),p
[i
].id
=i
,v
.pb(p
[i
].x
),v
.pb(p
[i
].x
+p
[i
].h
-1);sort(p
+1,p
+1+n
,cmp
);sort(v
.begin(),v
.end()); v
.erase(unique(v
.begin(),v
.end()),v
.end());se
=v
.size();for(int i
=1;i
<=n
;i
++){int x
=p
[i
].x
,h
=p
[i
].h
,id
=p
[i
].id
;mf(find(x
)+1,x
+h
-1); add(find(x
)+1);int pos
=find(x
+h
-1)+1;int mx
=ask(pos
);mf(find(x
)+1,mx
);ans
[p
[i
].id
]=sum(find(mx
))-sum(find(x
)+1)+1;}for(int i
=1;i
<=n
;i
++) printf("%d ",ans
[i
]);return 0;
}
總結
以上是生活随笔為你收集整理的CF56E Domino Principle 树状数组 + 简单dp的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
