IIT(ISM) Virtual Farewell D.Best Wishes !! DP，BFS

目标到达n，每次可以选择 *2，*3，或者 +1

问最少步数。

Solution 1 : 裸的的BFS ，可惜若对T组数据每次都memset会超时。

考虑离线做法。直接BFS出所有结点，存入答案。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+500;
const int inf = 1e6+10;
int n;
int vis[N],step[N];
int pre[N];
void init(){
    memset(vis,0,sizeof vis);
    memset(step,0,sizeof step);
    memset(pre,0,sizeof pre);
}
void bfs(){
    queue<int>Q;
    Q.push(1);
    while(!Q.empty()){
        int v,u=Q.front();Q.pop();
        if(u==inf)return;    
        v=u+1;
//        if(v>n)continue;
        if(v<=inf&&!vis[v]){
            Q.push(v);
            vis[v]=1;
            step[v]=step[u]+1;
            pre[v]=u;
        }
        v=2*u;
        if(v<=inf&&!vis[v]){
            Q.push(v);
            vis[v]=1;
            step[v]=step[u]+1;
            pre[v]=u;
        
        }
        v=3*u;
        if(v<=inf&&!vis[v]){
            Q.push(v);
            vis[v]=1;
            step[v]=step[u]+1;
            pre[v]=u;
    
        }
 
    }
}
 
int main(){
    int t;cin>>t;
    init();
    bfs();
    while(t--){
        scanf("%d",&n);
//        init();
//        int ans=bfs();
        printf("%d
",step[n]+1);
        vector<int>v;v.push_back(n);
        while(pre[n]){
//            printf("%d ",pre[n]);
            v.push_back(pre[n]);
            n=pre[n];
        }
        if (v.size() != 0)
        sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)printf("%d ",v[i]);
    puts("");
//    puts("");
    }
//    system("pause");
    return 0;
}

Solution 2: 考虑DP。

dp[n]表示到n的最少步数 。有 dp[n] = min(dp[n/2],dp[n/3],dp[n-1] ) + 1

仍然采用离线做法。  只是考虑如何输出最终方案？

很简单，考虑究竟是如何转移就行。

int dp[maxn];
 
void init() {
    dp[1] = 1;
    for (int i = 2; i <= maxn - 3; i++) {
        dp[i] = dp[i - 1];
        if (i % 2 == 0) {
            dp[i] = min(dp[i] , dp[i / 2]);
        }
        if (i % 3 == 0) {
            dp[i] = min(dp[i], dp[i / 3]);
        }
        dp[i]++;
    }
}
 
void print(int t) {
    vector<int> v;
    v.push_back(t);
    int n = t;
    if (n == 1) {
        puts("1"); return;
    }
    while (n != 1) {
        //printf("%d
", n);
        if (n % 2 == 0 && dp[n / 2] + 1 == dp[n]) {
             v.push_back(n / 2), n /= 2;
        }
        else if (n % 3 == 0 && dp[n / 3] + 1 == dp[n]) {
             v.push_back(n / 3), n /= 3;
        }
        else if(dp[n] == dp[n - 1] + 1) v.push_back(n - 1), n--;
    }
    for (int i = v.size() - 1; i >= 1; i--) printf("%d ", v[i]);
    printf("%d
", v[0]);
}
 
int main() {
    int T;
    int n;
    init();
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        printf("%d
", dp[n]);
        print(n);
    }
}