CFR Educational 16 E. Generate a String ( DP, SSSP )

Problem - E - Codeforces
首先我們知道這一般來說是很常見的最短路水題。但問題是 N = 1e7，顯然不給 logN 或足夠常數讓你乖乖玩 SSSP，所以我們考慮轉移邊的性質。首先我們考慮有哪些轉移的組合。一般之所以不能由左往右刷 dp 表是因為這題有反向邊，也許最小值會從後面傳回來。但仔細想想，哪些情況會傳回來？第一個我們可以排除掉 +1 後馬上 -1 的情況。我們進一步想，什麼時候正確的最短路徑必須要從較大的節點轉移過來，就會再發現，不會有必須要退兩步以上才有最短路徑的情況，因為如果要退兩步，那代表是先倍增過再退的( 不然不會從比較大的值來 )，但其實根本可以先退一步再倍增，就不需要事後退兩步了。因此我們得到結論，如果要從左到右刷過去，可以只刷三個節點，+1 / *2 / *2 - 1，因為 *2 之後最多只退一步不會丟失最短路徑。
似乎也有人硬是用 SPFA 跟怪怪的優化過的，真神秘。

void solve(){
    int N, X, Y; cin >> N >> X >> Y;
    vl dp( N + 100, LINF );
    dp[ 0 ] = 0;
    for( int i = 0; i < N; ++i ){
        upmin( dp[ i + 1 ], dp[ i ] + X );
        if( i * 2 < dp.size() )
            upmin( dp[ i * 2 ], dp[ i ] + Y );
        if( i * 2 - 1 < dp.size() )
            upmin( dp[ i * 2 - 1 ], dp[ i ] + Y + X );
    }
    cout << dp[ N ] << "\n";
}