本文主要是介绍poj 1769 dp + 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// 哎没想到dp啊，后续状态基于当前状态，当前状态不会影响后续状态，dp dp dp//// dp[i][j] 第i个sort的时候 最大数在j所需要的最短sort数则//// dp[i + 1][j] = dp[i][j] 当第i段sort[si,ti] 中 ti != j (即舍弃此sort)// dp[i + 1][j] = min(dp[i][j],dp[i][j'] + 1){si <= j' <= ti) ti == j}//// 当然dp[0][1] = 0，因为一个数不需要sort，其他无穷大。// 这就相当于在找一个[si,ti]中找到一个最小的dp 加上这第i段的sort的状态//// 这一步提示一下还是能想到的。但是复杂度仍然是nm过不了的，后面优化更是想不到啦////// 由于一般dp[i+1][j] = dp[i][j]，则可以直接去掉第一维度。只要在// ti的时候进行更新判断 dp[ti] = min(dp[j'] + 1 {si<= j' <= ti})//// 然后用线段树维护一下区间dp的最小值，然后更新一下就好了~~~~~//// 长知识啦，加油加油~~~~#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 50008;
const int maxm = maxn * 10;
const int INF = 0x7f7f7f7f;
int dp[maxn];
int s[maxm];
int t[maxm];struct SegmentTree{
#define lson(x) (x << 1)
#define rson(x) ((x << 1) | 1)int dat[maxn << 3];void init(){memset(dat,INF,sizeof(dat));}void push_up(int rt){dat[rt] = min(dat[lson(rt)],dat[rson(rt)]);}void update(int rt,int l,int r,int index,int x){if (l == r){dat[rt] = x;return ;}int M = l + (r - l) / 2;if (index <= M)update(lson(rt), l , M,index,x);elseupdate(rson(rt), M + 1,r,index,x);push_up(rt);}int query(int rt, int l,int r, int ql, int qr){if (ql <= l && r <= qr){return dat[rt];}int M = l + (r - l) / 2;int res = INF;if (ql <= M) res = min(res,query(lson(rt),l,M,ql,qr));if (M < qr) res = min(res,query(rson(rt),M + 1,r,ql,qr));return res;}
}it;int main(){int n,m;//freopen("1.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){for (int i = 0;i < m;i ++){scanf("%d%d",s + i,t + i);}memset(dp,INF,sizeof(dp));dp[1] = 0;it.init();it.update(1,1,n,1,0);for (int i = 0;i < m;i ++){int tmp = min(dp[t[i]],it.query(1,1,n,s[i],t[i] + 1) + 1);dp[t[i]] = tmp;it.update(1,1,n,t[i],tmp);}printf("%d\n",dp[n]);}return 0;
}
这篇关于poj 1769 dp + 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
