牛老闆(牛客練習賽87-C，搜尋優化)

牛老闆

思路：

打比賽的時候想的是dfs會逾時，應該會有更好的方法，就沒有去dfs，下次還是大膽一些，就算逾時了，也比不寫強，dfs從大到小去篩，中間對不可能優化res的情況直接剪枝就好，最後也是比較快的通過了

代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int N=2000007;
const int inf=0x3f3f3f3f3f3f3f3f;
vector<int>v;
int  n,m,k,t,q,p;
int a[N],vis[N],b[N],dp[N];
bool cmp(int a1,int b1){
    return a1>b1;
}
int res=0;//最優值
//還差多少錢，目前枚舉到紙币的位置，dfs目前值
void dfs(int rest,int pos,int ans){
    //到最後一位了，判完結束即可
    if(pos==v.size()-1){
        res=min(res,ans+rest);
        return ;
    }
    if(ans+rest/v[pos]>=res)return ;//剪枝
    //暴力dfs
    for(int i=rest/v[pos];i>=0;i--){
        dfs(rest-i*v[pos],pos+1,ans+i);
    }
}

signed main (){
    for(int i=1;i<=1e12;i*=6){
        v.push_back(i);
    }
    for(int i=9;i<=1e12;i*=9){
        v.push_back(i);
    }
    sort(v.begin(),v.end(),cmp);

    cin>>t;
    while(t--){
        cin>>n;
        res=inf;
        dfs(n,0ll,0ll);
        cout<<res<<"\n";
    }
    return 0;
}
           

當然 标準題解 是有漏洞的，它一直貪心地優先用面值比較大的紙币，就有些資料通不過了，給一個hack： 5 ∗ 6 9 + 3 ∗ 9 7 = 64737387 5*6^9+3*9^7=64737387 5∗69+3∗97=64737387，是以64737387答案至多是8，标程輸出了9

标準題解的代碼：

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
unordered_map<ll,int>f;
vector<ll>v6,v9;
int F(ll n)
{
    if(n==0||f[n]) return f[n];
    f[n]=inf;
    int pos=upper_bound(v6.begin(),v6.end(),n)-v6.begin()-1;
    if(pos>=0)
        f[n]=min(f[n],F(n-v6[pos])+1);
    pos=upper_bound(v9.begin(),v9.end(),n)-v9.begin()-1;
    if(pos>=0)
        f[n]=min(f[n],F(n-v9[pos])+1);
    if(n<=5) f[n]=min(f[n],F(n-1)+1);
    return f[n];
}
int main()
{
    for(ll x=6;x<=1000000000000ll;x*=6) v6.push_back(x);
    for(ll x=9;x<=1000000000000ll;x*=9) v9.push_back(x);
    int t;scanf("%d",&t);
    while(t--)
    {
        ll n;scanf("%lld",&n);
        printf("%d\n",F(n));
    }
}