题解 P3527 【[POI2011]MET-Meteors】

hfctf0210 · 2017-10-31 14:57:39 · 题解

这道题用斐波那契数列+二分就可以解决：

思路：用斐波那契二分思想，求出1,1,2一直到不超过10亿的所有斐波那契数，再进行二分

代码：

#include<iostream>
using namespace std;
int t,n,r,a[10001][3],f[10001];
int main()
{
    int i,j,x,max1;
    cin>>t>>n>>r;
    for(i=1;i<=n;i++)
    {
        cin>>a[i][0]>>x>>a[i][2];
        a[i][1]=x+r;
    }
    for(i=1;i<n;i++)
    for(j=i+1;j<=n;j++)
    if(a[i][0]>a[j][0])
    {
        swap(a[i][0],a[j][0]);
        swap(a[i][1],a[j][1]);
        swap(a[i][2],a[j][2]);
    }
    f[n]=a[n][2];
    for(i=n-1;i>=1;i--)
    {
        max1=0;
        for(j=i+1;j<=n;j++)
        if(a[i][1]<=a[j][0]&&f[j]>max1)
        max1=f[j];
        f[i]=max1+a[i][2];
    }
    max1=0;
    for(i=1;i<=n;i++)
    if(f[i]>max1)
    max1=f[i];
    cout<<max1<<endl;
}

注：1、递推得到关系式f(n)=f(n-1)+f(n-2) 2、取出小于n的项存入数组

3、二分+乱搞，搞搞就出来了

4、我的代码太乱，请勿借鉴