P3957 [NOIP2017 普及组] 跳房子

50分代码

 1 //P3957 [NOIP2017 普及组] 跳房子
 2 #include<iostream>
 3 #include<queue>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long ll;
 8 int n,d,k;
 9 int a[500010][2];
10 ll f[500010],sum=0;
11 bool check(int g) {
12     int l=max(1,d-g),r=d+g;
13     //cout<<"%%%"<<l<<' '<<r<<endl;
14     memset(f,-127,sizeof f);
15     f[0]=0;
16     for(int i=1; i<=n; i++) { //每个格子
17         int td;
18         for(int j=0; j<i; j++) { //当前格子的前面格子,从小到大去寻找 
19             td=a[i][0]-a[j][0];
20             //cout<<"***"<<j<<" "<<td<<endl;
21             if(td>=l&&td<=r) {
22                 f[i]=max(f[i],f[j]+a[i][1]);
23             }
24             if(f[i]>=k) return true;
25             if(td<l) break;
26         }
27     //    cout<<i<<' '<<f[i]<<endl;
28     }
29     return false;
30 }
31 
32 int main() {
33     scanf("%d %d %d",&n,&d,&k);
34     for(int i=1; i<=n; i++) {
35         scanf("%d %d",&a[i][0],&a[i][1]);
36         if(a[i][1]>0) sum+=a[i][1];
37     }
38     if(sum<k) { //所有的正分加起来都不够希望获得的分数
39         printf("-1");
40         return 0;
41     }
42     //二分
43     int l=0,r=max(0,a[n][0]-d);
44     while(l<r) {
45         //cout<<'*'<<l<<' '<<r<<endl;
46         int mid=(l+r)/2;
47         if(check(mid)) r=mid;
48         else l=mid+1;
49     }
50     printf("%lld",l);
51     return 0;
52 }

80分代码

18行，显然我们要取得更大的f[i]的值。而i越大，f[i]的值更大的可能性更高，所以可以从大到小去寻找。但是并不严谨，只是可能性更高一些。

//P3957 [NOIP2017 普及组] 跳房子
#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
int n,d,k;
int a[500010][2];
ll f[500010],sum=0;
bool check(int g) {
    int l=max(1,d-g),r=d+g;
    //cout<<"%%%"<<l<<' '<<r<<endl;
    memset(f,-127,sizeof f);
    f[0]=0;
    for(int i=1; i<=n; i++) { //每个格子
        int td;
        for(int j=i-1; j>=0; j--) { //当前格子的前面格子，从大到小寻找 
            td=a[i][0]-a[j][0];
            //cout<<"***"<<j<<" "<<td<<endl;
            if(td>=l&&td<=r) {
                f[i]=max(f[i],f[j]+a[i][1]);
            }
            if(f[i]>=k) return true;
            if(td>r) break;
        }
        //    cout<<i<<' '<<f[i]<<endl;
    }
    return false;
}

int main() {
    scanf("%d %d %d",&n,&d,&k);
    for(int i=1; i<=n; i++) {
        scanf("%d %d",&a[i][0],&a[i][1]);
        if(a[i][1]>0) sum+=a[i][1];
    }
    if(sum<k) { //所有的正分加起来都不够希望获得的分数
        printf("-1");
        return 0;
    }
    //二分
    int l=0,r=max(0,a[n][0]-d);
    while(l<r) {
        //cout<<'*'<<l<<' '<<r<<endl;
        int mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%lld",l);
    return 0;
}

100分代码

显然18行去求f[i]，可以用更快的方式。用两个指针，直接指向能够跳跃的区间。

 1 //P3957 [NOIP2017 普及组] 跳房子
 2 #include<iostream>
 3 #include<queue>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long ll;
 8 int n,d,k;
 9 int a[500010][2];
10 ll f[500010],sum=0;
11 bool check(int g) {
12     int l=max(1,d-g),r=d+g;
13     //cout<<"%%%"<<l<<' '<<r<<endl;
14     memset(f,-127,sizeof f);
15     f[0]=0;
16     int pl=0,pr=0; //两端
17     for(int i=1; i<=n; i++) { //每个格子
18         while(a[i][0]-a[pl][0]>r) pl++;
19         while(a[i][0]-a[pr][0]>=l) pr++;
20         for(int j=pr-1; j>=pl; j--) {
21             f[i]=max(f[i],f[j]+a[i][1]);
22             if(f[i]>=k) return true;
23         }
24     }
25     return false;
26 }
27 
28 int main() {
29     scanf("%d %d %d",&n,&d,&k);
30     for(int i=1; i<=n; i++) {
31         scanf("%d %d",&a[i][0],&a[i][1]);
32         if(a[i][1]>0) sum+=a[i][1];
33     }
34     if(sum<k) { //所有的正分加起来都不够希望获得的分数
35         printf("-1");
36         return 0;
37     }
38     //二分
39     int l=0,r=max(0,a[n][0]-d);
40     while(l<r) {
41         //cout<<'*'<<l<<' '<<r<<endl;
42         int mid=(l+r)/2;
43         if(check(mid)) r=mid;
44         else l=mid+1;
45     }
46     printf("%lld",l);
47     return 0;
48 }