因為這一題寫的人不多, 所以我也找不到有測資或是其他能夠參考的想法...Orz

根據提示是DFS,  每次可以選Ctrl C or Ctrl V 兩種可以選擇

剪枝的方法是(1)目前已經印出的量>=需要的量(2)複製版上的量>=需要的量(3)次數多於目前紀錄的最小次數

因為不會出現連續兩個Ｃ,沒意義

以下是根據上述的想法寫的程式碼, 想問一下有哪邊是我沒注意到的嗎？

#include<iostream>
#include<vector>
using namespace std;

int N, Mintimes;
char sym[2]={'C','V'};
vector< vector<bool> > ans;
vector<bool>op;

void DFS(int Done, int Store, int times){
    if(Done==N){
       if(times<Mintimes){
           Mintimes=times;
           ans.clear();
           ans.push_back(op);
       }
       else if(times==Mintimes)
           ans.push_back(op);
       }
    if(Done>=N or Store>=N or times>=Mintimes) return;
    // 選擇 Ctrl C, 不應該會有連續兩個C, 沒意義
    if(Done!=Store){
        op.push_back(0);
        DFS(Done,Done,times+1);
        op.pop_back();
    }
    // 選擇 Ctrl V
    op.push_back(1);
    DFS(Done+Store,Store,times+1);
    op.pop_back();
}
int main(){
    while(cin>>N){
        Mintimes=0x7fffffff;
        ans.clear();
        op.push_back(0);
        op.push_back(1);
        DFS(2,1,2);
        // Output
        cout<<"min : "<<Mintimes<<"\nway : "<<ans.size()<<endl;
        for(int i=0;i<ans.size();i++){
            cout<<"Ctrl C + V";
            for(int j=2;j<ans[i].size();j++)
                cout<<" + "<<sym[ans[i][j]];
            cout<<endl;
        }
    }
}

我回應自己的問題好了....當作個紀錄

雖然做DFS報蒐的時候已經先讓C執行(如果可以的話)在選擇V, 但找到的順序似乎不一定會保證C會在V前面

所以只要找完全部之後再sort確保符合題目要求即可, 時間是3.8s

我花了 5 年才想到 python 解法。...