2018.1.29 [AtCoder Beginner Contest 087-C] 문제풀이 보고서(단순dp)

C - Candies

Time limit : 2sec/ Memory limit : 256MB
Score : 300 points

Problem Statement

We have a 2×N grid. We will denote the square at the i-th row and j-th column (1≤i≤2, 1≤j≤N) as (i,j).
You are initially in the top-left square, (1,1). You will travel to the bottom-right square, (2,N), by repeatedly moving right or down.
The square (i,j) contains Ai,j candies. You will collect all the candies you visit during the travel. The top-left and bottom-right squares also contain candies, and you will also collect them.
At most how many candies can you collect when you choose the best way to travel?

Constraints

1≤N≤100
1≤Ai,j≤100 (1≤i≤2, 1≤j≤N)

Input

Input is given from Standard Input in the following format:

N
A1,1 A1,2 … A1,N
A2,1 A2,2 … A2,N

Output

Print the maximum number of candies that can be collected.

Sample Input 1

Copy

5
3 2 2 4 1
1 2 2 2 1

Sample Output 1

Copy

14

The number of collected candies will be maximized when you:
move right three times, then move down once, then move right once.

Sample Input 2

Copy

4
1 1 1 1
1 1 1 1

Sample Output 2

Copy

5

You will always collect the same number of candies, regardless of how you travel.

Sample Input 3

Copy

7
3 3 4 5 4 5 3
5 3 4 4 2 3 2

Sample Output 3

Copy

29

Sample Input 4

Copy

1
2
3

Sample Output 4

Copy

5

[제목 대의]
2*N 칸으로 각 칸마다 양초의 수량이 다릅니다.매번 오른쪽이나 아래로 내려가기만 하면 (1,1)에서 (2,N)까지 최대 몇 개의 촛불(처음과 끝 포함)을 모을 수 있는지 물어본다.
[문제풀이 사고방식]
입문 DP, 2*N으로 간소화, 상태 이동 방정식: dp[i][j]=max(dp[i-1][j], dp[i][j-1])+a[i][j]
[문제풀이 코드]

#include 
#include 
#include 
using namespace std;
//dp   dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j]
const int maxn=1e2+10; 
int n;
int a[maxn][maxn];
int dp[maxn][maxn];

int max(int a,int b)
{
	return a>b?a:b;
 } 

void solve()
{
	dp[1][1]=a[1][1];
	for(int i=1;i<=2;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i==1)
				dp[i][j]=dp[i][j-1]+a[i][j];
			else
				dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j]; 
		}
	}
} 
int main()
{
	while(~scanf("%d",&n))
	{
	
	memset(a,0,sizeof(a));
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=2;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	solve();
	printf("%d
",dp[2][n]);
}
	return 0;
}

[수확과 반성]
첫 번째 작은 경기에서 실전에 dp를 응용했는데 신을 보면 모두 dp초로 사고방식이 정확하다는 것을 설명한다.상태 이동 방정식을 잘 쓰면 돼.