BOJ-17291子


に近づく
  • 動的計画法
  • dp[i]={i翌年の星数,i翌年の虫数}
    #include <iostream>
    using namespace std;
    typedef pair<int, int> p;
    p arr[30];
    int main() {
    	int n; cin >> n;
    	arr[1] = arr[2] = arr[3] = { 1,0 };
    	arr[4] = { 1,1 };
    	for (int i = 2; i <= n + 1; i++) {
    		if (i % 2 == 1) {
    			for (int j = i + 1; j <= i + 3 && j <= n + 1; j++) arr[j].first += arr[i].first;
    			arr[i + 3].second += arr[i].first;
    		}
    		else {
    			for (int j = i + 1; j <= i + 4 && j <= n + 1; j++) arr[j].first += arr[i].first;
    			arr[i + 4].second += arr[i].first;
    		}
    		arr[i].first = arr[i].first * 2 - arr[i].second;
    	}
    	cout << arr[n].first;
    	return 0;
    }
    }