POJ 3176 Cow Bowling
問題文はこちら
典型DP
蟻本にのってた。
配列でもぐもぐする。
#include <cstdio> #include <algorithm> using namespace std; int bow[353][353] = {0}; int dp[353][353] = {0}; int n = 0; int main(){ scanf("%d",&n); for(int i = 0;i < n;i++){ for(int j = 0;j < i + 1;j++){ scanf("%d",&bow[i][j]); } } for(int i = 1;i <= n;i++){ int j = 0; dp[i][j] = dp[i-1][j] + bow[i-1][j]; j++; for(;j < i - 1;j++){ dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + bow[i-1][j]; } dp[i][j] = dp[i-1][j-1] + bow[i-1][j]; } int ans = dp[n][0]; for(int i = 0;i < n;i++){ ans = max(ans,dp[n][i]); } printf("%d\n",ans); }