acmicpc_14585(사수빈탕)

전형적인 dp문제 중 한문제였다. 위에서 내려올때와 옆에서 올때의 두가지 경우로 dp[i][j]가 결정된다.

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int arr[301][301];
int dp[301][301];
int k;

int main() {
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		arr[x][y] = m - (x + y);
		if (arr[x][y] < 0) {
			arr[x][y] = 0;
		}
		dp[x][y] = arr[x][y];

	}
	
	for (int i = 1; i < 300; ++i) {
		for (int j = 1; j < 300; ++j) {
			
			dp[i][j] = arr[i][j] + max(dp[i - 1][j], dp[i][j - 1]);
			k = max(dp[i][j], k);
		}
	}
	cout << k;

}