买西瓜吃，每个西瓜有两个参数，一个是p代表价格，一个是t代表能吃几天，要求n天每天都能吃西瓜，而且如果你今天买了，以前买的还没吃完 那么都得扔了，求最小花费，还真想不到用线段树+DP，最后看了一下别人的标题，想了一下，DP方程挺好推的，线段树也只是单点查询，
?
#include #include #include #include #include #include //#include #include #include #include #include #include #include #define ll long long #define eps 1e-8 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; const int N = 50005 + 5; typedef struct Node { int l,r; int mark;//biaoji ll pri; }; Node tree[N << 2]; ll p[N],t[N]; void build(int l,int r,int id) { tree[id].l = l; tree[id].r = r; tree[id].mark = 0; tree[id].pri = INF; if(l == r)return; int mid = (l + r)>>1; build(l,mid,id<<1); build(mid+1,r,id<<1|1); } void push_up(int id) { if(tree[id].mark) { tree[id<<1].mark = 1; tree[id<<1|1].mark = 1; tree[id].mark = 0; tree[id<<1].pri = min(tree[id].pri,tree[id<<1].pri); tree[id<<1|1].pri = min(tree[id].pri,tree[id<<1|1].pri); } } void update(int l,int r,int id,ll cost) { if(l <= tree[id].l && r >= tree[id].r) { tree[id].pri = min(tree[id].pri,cost); tree[id].mark = 1;return ; } push_up(id); int mid = (tree[id].l + tree[id].r)>>1; if(r <= mid)update(l,r,id<<1,cost); else if(l > mid)update(l,r,id<<1|1,cost); else { update(l,mid,id<<1,cost); update(mid+1,r,id<<1|1,cost); } } ll query(int pos,int id) { if(pos == 0)return 0; if(tree[id].l == tree[id].r) return tree[id].pri; push_up(id); int mid = (tree[id].l + tree[id].r)>>1; if(pos <= mid) return query(pos,id<<1); else return query(pos,id<<1|1); } int main() { int n; while(scanf("%d",&n) == 1) { for(int i=1;i<=n;i++) scanf("%lld",&p[i]); for(int i=1;i<=n;i++) scanf("%lld",&t[i]); build(1,n,1); for(int i=1;i<=n;i++) { ll tmp = query(i-1,1); update(1,i + t[i] - 1,1,tmp + p[i]); } ll ans = query(n,1); printf("%lld\n",ans); } return 0; }