Aroma's Search

D. Aroma's Search

首先根据数据范围可以知道,数据点最多只有50多个,因此这道题可以暴力来解

另外我们还知道,最优解的数据点一定是连续的,因为第\(i+1\)个点必然在第\(i\)个点的右上方。

因为其数据范围很小,所以我们只需要遍历所有的情况即可。

代码:

// Created by CAD on 2020/1/19.
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll ax,ay,bx,by,xs,ys,X,Y,t;
ll x[60],y[60];
const ll inf=1e17;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> x[0] >> y[0] >> ax >> ay >> bx >> by;
    cin>>xs>>ys>>t;
    int n=0;
    while((inf-bx)/ax>=x[n]&&(inf-by)/ay>=y[n])
        n++,x[n]=(ax * x[n-1] + bx),y[n]=(ay * y[n-1] + by);
    int ans=0;
    for(int i=1;i<=n+1;++i)
        for(int l=0;l+i-1<=n;++l)
        {
            int r=l+i-1;
            ll len=x[r]-x[l]+y[r]-y[l];
            ll dl=abs(xs-x[l])+abs(ys-y[l]);
            ll dr=abs(xs-x[r])+abs(ys-y[r]);
            if(dl<=t-len||dr<=t-len) ans=max(ans,i);
        }
    cout<<ans<<endl;
    return 0;
}
上一篇:Spring IOC——常用注解(Component)


下一篇:暴力,贪心——cf1292B