首页 > 代码库 > 美梦1(JSOI2014,算法艺术与信息学竞赛)

美梦1(JSOI2014,算法艺术与信息学竞赛)

【问题描述】

  这天晚上,约翰做了个奇怪的美梦。他拥有了分别分布在N座高高低低的山上的N个池塘,N座山连成一条直线,从左往右第i座山的高度是Hi。池塘中的鱼都是他请专家运用科学的方法专门养殖的,为了保护每个池塘的生态环境,他现在要在这N座山上建造若干个看护点。约翰是个很节约的人,在第i座山建造看护点的花费为Ci。假设在第i座山建造一个看护点,则往左或者往右第一座不比这座山低的山将挡住看护的视线。譬如说: {Hi} = {1 4 4 5 7 2}表示第一座山高度为1,第二座山高度为4。。。 如果在第1座山建造一个看护点,则可以看护第1,2两个池塘。如果在第5座山上建造一个看护点,则左右的池塘都能被看护到。如果在第3座山上建造一个看护点,则能够看护到第2,3,4个池塘。

Problem Task:

  要求能够看护到所有的池塘,建造看护点的最小代价是多少。即建造看护点的山对应的花费Ci之和最小。

Problem Input:

  第一行包含一个正整数N,N满足1<=N<=1000000。

  第二行包含N个正整数,第i个正整数Hi满足1<=Hi<=10^9,表示第i座山的高度

  第三行包含N个正整数,第i个正整数Ci满足1<=Ci<=10^9,表示在第i座山建造看护点的代价为Ci

Problem Output:

  一行包含一个正整数C,表示最小的代价。

Problem Input Example:

3

1 1 1

2 2 2

Problem output Example:

2

 

这题是个很裸的动归  , 不过数据范围有些怕人... 

Way1:设f[i] 表示 看护1~i座山所需最小花费,则显然有f[i] = min{f[k] + C_t} (Lt<=k<=Rt = i)

不难发现可以用线段树维护最优值,单点修改,区间查询。

Way2: 设f[i] 表示 看护1~i座山,且第i座山上修建看护点 ,则显然有 f[i] = min{f[j]} + C_i (R_j >= L_i )

不难发现也可以偶那个线段树维护,单点查询,区间修改

Codes:

 1 #include<set> 2 #include<queue> 3 #include<cstdio> 4 #include<vector> 5 #include<cstring> 6 #include<cstdlib> 7 #include<iostream> 8 #include<algorithm> 9 using namespace std;10 const int N = 1000010;11 typedef long long lld;12 const lld inf = lld(21474836470000000);13 #define Ch1 (i<<1)14 #define Ch2 (Ch1|1)15 #define For(i,n) for(int i=1;i<=n;i++)16 #define Rep(i,l,r) for(int i=l;i<=r;i++)17 #define Down(i,r,l) for(int i=r;i>=l;i--)18 struct tnode{19     int l,r,mid;20     lld min;21 }T[N<<2];22 int Left[N],Right[N],top,n,H[N],C[N],st[N];23 lld f[N];24 25 void read(int &v){26     int num = 0; char ch = getchar();27     while(ch>9||ch<0) ch = getchar();28     while(ch>=0&&ch<=9){29         num = num * 10 + ch - 0;30         ch = getchar();31     }32     v = num;33 }34 35 void init(){36     read(n);37     For(i,n) read(H[i]);38     For(i,n) read(C[i]);39     st[top=1] = 0;H[0] = H[n+1] = 2147483647;40     For(i,n){41         while(H[st[top]]<H[i]) top--;42         Left[i] = max(st[top],1);43         st[++top] = i;44     }45     st[top=1] = n+1;46     Down(i,n,1){47         while(H[st[top]]<H[i]) top--;48         Right[i] = min(st[top],n);49         st[++top] = i;50     }51 }52 53 void Build(int l,int r,int i){54     T[i].l = l;T[i].r = r;T[i].mid = (l+r)>>1;55     T[i].min = inf;56     if(l==r) return;57     Build(l,T[i].mid,Ch1); Build(T[i].mid+1,r,Ch2);58 }59 vector< pair<int,int> > G[N];60 //f[i] = min{f[t] + cost[k]}61 62 void Modify(int i,int x,lld delta){63     if(T[i].l==T[i].r){64         T[i].min = delta;65         return;66     }67     if(x<=T[i].mid)  Modify(Ch1,x,delta);68     else             Modify(Ch2,x,delta);69     T[i].min = min(T[Ch1].min,T[Ch2].min);70 }71 72 lld query(int l,int r,int i){73     if(l<=T[i].l&&T[i].r<=r) return T[i].min;74     if(r<=T[i].mid)  return query(l,r,Ch1);75     if(l>T[i].mid)   return query(l,r,Ch2);76     return min(query(l,T[i].mid,Ch1) , query(T[i].mid+1,r,Ch2));77 }78 79 int main(){80     freopen("fish1.in","r",stdin);81     freopen("fish1.out","w",stdout);82     init();83     Build(0,n,1);84     Modify(1,0,0);85     For(i,n){86         G[Right[i]].push_back(make_pair(Left[i],C[i]));87         G[i].push_back(make_pair(Left[i],C[i]));88     }89     For(i,n){90         f[i] = inf;91         for(int j = 0;j<G[i].size();j++) 92            f[i] = min(f[i],query(G[i][j].first-1,i,1) + G[i][j].second);93         Modify(1,i,f[i]);94     }95     cout<<f[n]<<endl;96     return 0;97 }