Codeforces 675E Trains and Statistic(DP + 贪心 + 线段树)

时间:2021-10-01 19:26:52

题目大概说有n(<=10W)个车站,每个车站i卖到车站i+1...a[i]的票,p[i][j]表示从车站i到车站j所需买的最少车票数,求所有的p[i][j](i<j)的和。

好难,不会写。。

  • dp[i]表示Σp[i][j](j>i)
  • 转移是dp[i]=dp[k]+(n-i)-(a[i]-k),其中k是i能直接买到的站中能直接买到最远的站,即a[k]=max(a[i+1]...a[a[i]]),这个可以用线段树快速查询

为什么从k转移?因为i+1...a[i]中除了k外能直接买到的车站都是k的子集,贪心地选择能延伸最远的k一定是没错的。

为什么转移方程是这样?dp[i],就是表示从i出发到达各个j(j>i)城市所需最少票数和,而这(n-i)个车站,对于在a[i]范围内只要从车站i买一张车票就直达了,对于大于a[i]的需要买一张车票到车站k再转车,所以就是dp[k]+(n-i);不过在dp[k]里面重复算了,要去k+1...a[i]范围的车站,明明可以直达却先到达k再转车,这多买了一张车票,所以减去(a[i]-k)。

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 #define MAXN 111111
 5 
 6 struct Node{
 7     int mmm,idx;
 8     Node():mmm(0){}
 9 }tree[MAXN<<2];
10 int x,y,N;
11 void update(int i,int j,int k){
12     if(i==j){
13         tree[k].mmm=y;
14         tree[k].idx=i;
15         return;
16     }
17     int mid=i+j>>1;
18     if(x<=mid) update(i,mid,k<<1);
19     else update(mid+1,j,k<<1|1);
20     if(tree[k<<1].mmm>tree[k<<1|1].mmm){
21         tree[k]=tree[k<<1];
22     }else{
23         tree[k]=tree[k<<1|1];
24     }
25 }
26 Node query(int i,int j,int k){
27     if(x<=i && j<=y){
28         return tree[k];
29     }
30     int mid=i+j>>1;
31     Node ret;
32     if(x<=mid){
33         Node tmp=query(i,mid,k<<1);
34         if(ret.mmm<tmp.mmm) ret=tmp;
35     }
36     if(y>mid){
37         Node tmp=query(mid+1,j,k<<1|1);
38         if(ret.mmm<tmp.mmm) ret=tmp;
39     }
40     return ret;
41 }
42 
43 int a[MAXN];
44 long long d[MAXN];
45 int main(){
46     int n;
47     scanf("%d",&n);
48     for(N=1; N<n; N<<=1);
49     for(int i=1; i<n; ++i){
50         scanf("%d",a+i);
51         x=i; y=a[i];
52         update(1,N,1);
53     }
54     x=n; y=n;
55     update(1,N,1);
56     for(int i=n-1; i>=1; --i){
57         x=i+1; y=a[i];
58         Node tmp=query(1,N,1);
59         d[i]=d[tmp.idx]+n-i-(a[i]-tmp.idx);
60     }
61     long long res=0;
62     for(int i=1; i<=n; ++i){
63         res+=d[i];
64     }
65     printf("%lld",res);
66     return 0;
67 }