BOJ 193:この親水性-C++

6951 ワード
DP boj テキストリンク

自分の手で


  • 問題は最終的にフィボナッチ点火式で解決された.
    しかし、これは問題の本質を明らかにしていない
  • key point! (本質的な解釈を理解する)
    1)この桁数では、0で終わる要素に0と1を加算できます.
    ex) 100 -> 101 / 1002)この桁数の1で終わる要素は0しか加算できません
    ex) 101 -> 100

    • コード#コード#

    #include <string>
#include <vector>
#include <iostream>
using namespace std;
// d[i][1] = i 자리수 일 때 끝이 1인 개수
// d[i][0] = i 자리수 일 때 끝이 0인 개수
long long d[92][2]; 
int N;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    d[1][1] = 1; 
    d[2][0] = 1; 
    d[3][0] = 1; d[3][1] = 1;
    for(int i=4;i<=N;i++)
    {
        d[i][0] = d[i-1][0] + d[i-1][1];
        d[i][1] = d[i-1][0];
    }
    cout << d[N][0] + d[N][1];
    return 0;
}
  • テーブル定義D[i][0] = i 자리수 2진수 중 0으로 끝나는 요소의 개수 D[i][1] = i 자리수 2진수 중 1으로 끝나는 요소의 개수
  • 点火式D[i][0] = D[i-1][0] + D[i-1][1] D[i][1] = D[i-1][0]
  • 点火式について
    ex)i4が4の場合、1000/1010|の3つのケースが発生します.
    端点が0の要素には、0と1を後で追加できます.
    末尾1の要素の後に0を追加します.
    すなわち、1001->1000/10000      10001 -> 1010 / 10100      10101->1001!
    結果、10010はD[5][0](端点0=前位数の0要素数+前位数1の数)D[4][0] + D[4][1]はD[5][1](端点が1=前桁が0の要素数)
    • 標準差とbootstrap信頼区間の違い
    ツリー(Tree)