D - 三角パズル
D: 三角パズル - WUPC 2012 | AtCoder
・DP
#include <iostream> #include <cstdio> #include <map> #include <vector> #include <cstring> #include <algorithm> #include <list> #include <stack> #include <queue> using namespace std; typedef list<int> L; typedef pair <int,int> P; typedef vector<int> V; typedef queue<int> Q; typedef stack<int> S; typedef map<string,int> M; int main() { int dp[101][101]; int n[101][101]; int N; cin >> N; for (int i = 0; i <= N; i++) for (int j = 1; j <= i; j++) cin >> n[i][j]; int res = 0; dp[0][1] = n[0][1]; for (int i = 1; i <= N; i++) { for (int j = 1; j <= i; j++) { dp[i][j] += (n[i][j] + max(dp[i - 1][j], dp[i - 1][j - 1])); if (i == N) res = max(res, dp[i][j]); } } cout << res << endl << endl; for (int i = 0; i <= N; i++) { cout << endl; for (int j = 0; j <= N; j++) { cout << dp[i][j] << " "; } } return 0; }