Segmantation fault 11

c++でコードを書いていると出くわすのがこの
「 Segmantation fault 11　」　
これは踏み入れてはいけないメモリ領域に踏み込んだ時や、再帰が深すぎる時に起こるらしい。(メモリ違反・再帰深い)

今回はナップサック問題を解いている時に発生した。
main関数内でスタックオーバーフローを起こしていたので、変数を全てグローバル変数とすることで解決した。

「core」を使った発生場所の特定などもできるみたい。
また詳しく調べてみようと思う。

動的計画法part1

AtcoderさんのDPまとめコンテストのC問題　記録
今回はdpで最大値を求める問題。
それぞれのテーブルの値の最大値はどのように求められるのか意識してコードを書く必要がある。
この問題ではa,b,cは2回連続は使えない。

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int a[100000], b[100000], c[100000];
    for(int i = 0; i < n; i++){ 
        cin >> a[i] >> b[i] >> c[i];
    }

    int dp[3][100000];

    dp[0][0] = a[0];
    dp[1][0] = b[0];
    dp[2][0] = c[0];

    for(int j = 1; j < n; j++){
        dp[0][j] = max(dp[1][j-1],dp[2][j-1]) + a[j];
        dp[1][j] = max(dp[0][j-1], dp[2][j-1]) + b[j];
        dp[2][j] = max(dp[0][j-1], dp[1][j-1]) + c[j];
    }

    cout << max(dp[0][n-1], max(dp[1][n-1],dp[2][n-1]));
    return 0;
}

ブログ始めました！

ブログ始めました！

日々のプログラミング勉強の記録など、日々の備忘録をつらつら書いていきたいと思います。

この機会に日本語力も鍛えられたらなと思っています！

さて、早速今日は動的計画法についてです。

競技プログラミングを始めて約3週間が経ちました。

いろんなアルゴリズムに手を焼いている中で、動的計画法(Dynamic Programming)はなかなかの強者です。

理解したと思いきや、応用問題に出くわすとすぐ間違えてしまいます。

おそらく全然理解できていないのでしょう。とても悔しいです。

今はAtcoderさんのDPまとめコンテストという問題を解いています。

26問も動的計画法に絞った問題が揃っており、先人の先輩方のコードをみて勉強できるので学習が捗ります。

習うより慣れろ！今週中には26問終わらせたいですね。

がんばります！