[NOIP2017 普及组] 跳房子

 1 #include
 2 using namespace std;
 3 namespace _xzy
 4 {
 5     typedef long long ll;
 6     inline int read()
 7     {
 8         int sm=0,flag=1;
 9         char ch=getchar();
10         while(ch<'0'||ch>'9'){if(ch=='-')flag=-1;ch=getchar();}
11         while(ch>='0'&&ch<='9'){sm=(sm<<1)+(sm<<3)+(ch^48);ch=getchar();}
12         return sm*flag;
13     }
14     inline void write(ll x)
15     {
16         if(x<0){putchar('-');x=-x;}
17         else if(x>9)write(x/10);
18         putchar(x%10+'0');
19     }
20     const ll N=500002;
21     ll n,d,k,ans=1e9,maxn;
22     ll f[N][2];
23     bool vis[N];
24     struct node
25     {
26         ll xi,si;
27     }e[N];
28     int check(ll g)
29     {
30         for(ll i=1;i<=n;++i)
31         {
32             f[i][1]=f[i][0]=-1e9;
33             vis[i]=0;
34         }
35 //f[i][0]表示前i个格子且第i个格子没入选时，获得的最大分数
36 //f[i][0]直接继承前面的最大分数就可以了 
37 //f[i][1]表示前i个格子且第i个格子入选时，获得的最大分数
38 //f[i][1]既然第i个格子入选了，那么它肯定是从之前的一个格子跳过来的
39 //这时候就枚举从哪一个格子跳过来的就可以了
40 //于是退出转移方程
41 //f[i][0]=max(f[i-1][0],f[i-1][1])
42 //f[i][1]=max(f[i][1],f[j][1]+e[i].si) 
43 //要注意能从第j个格子跳过来，这说明第j个格子已经计算过了
44 //如果没有计算过，那么是不能转移的 
45         vis[0]=1;
46         for(ll i=1;i<=n;++i)
47         {
48             f[i][0]=max(f[i-1][0],f[i-1][1]);
49             for(ll j=i-1;j>=0;--j)
50             {
51                 if(d+g+e[j].xibreak;
52                 if(e[j].xi+d-g<=e[i].xi&&e[j].xi+d+g>=e[i].xi&&vis[j])
53                 {
54                     f[i][1]=max(f[i][1],f[j][1]+e[i].si);
55                     vis[i]=1;
56                 }
57             }
58             if(f[i][0]>=k||f[i][1]>=k)return 1;
59         }
60         return 0;
61     }
62     void My_main()
63     {
64         n=read();d=read();k=read();
65         for(ll i=1;i<=n;++i)
66         {
67             e[i].xi=read();e[i].si=read();
68         }
69         ll left=0,right=1005;//不要开太大，会T掉 
70         while(left<=right)//二分，找答案g 
71         {
72 //g的值越大，机器人能够弹跳的范围就越大，相应的，获得分数的机会就越多，达到想要分数就越可能
73 //相应的，g的值越小，达到想要分数的可能就越小
74 //因此，二分的单调性在这里 
75             ll mid=(left+right)>>1;
76             if(check(mid))
77             {
78                 ans=min(ans,mid);//如果该mid能够使机器人获得想要的分数，那么该值是可行的 
79                 right=mid-1;
80             }
81             else left=mid+1;
82         }
83         if(ans==1e9)write(-1);
84 //如果ans没有更改，那么就说明没有获得相应分数的可能，输出-1 
85         else write(ans);
86     }
87 }
88 int main()
89 {
90     _xzy::My_main();
91     return 0;
92 }