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;
}
}
Reference
この問題について(BOJ-17291子), 我々は、より多くの情報をここで見つけました https://velog.io/@hschoi1104/BOJ-17291-새끼치기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol