14585

해결방법

다이나믹 프로그래밍

dp[x][y] : x,y에 있을 때 먹을 수 있는 최대 사탕의 갯수

dp[x][y] = max(dp[x+1][y], dp[x][y]) + current(x,y) 남아있는 사탕 갯수

아래는 소스코드이다.

#include <iostream> 

#include <iterator>

#include <algorithm> 

#include <vector>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <string>

#include <cmath>

#include <cstdio>

#include <cstring>

using namespace std;

#define MOD 1000000007

#define INF 2147483647

#define LNF 9223372036854775807

#define pb push_back

#define mp make_pair

typedef long long ll;

typedef unsigned long long ull;

int n,m,data[301][301],dp[301][301];

int solve(int x, int y){

if(x>300 || y>300) return 0;

int &ret = dp[x][y];

if(ret != -1) return ret;

ret = max(solve(x+1,y),solve(x,y+1))+data[x][y]*(m-x-y<0?0:m-x-y);

return ret;

}

int main () {

freopen("sample.txt", "r", stdin);

scanf("%d%d",&n,&m);

for(int i=0,x,y;i<n;i++){

scanf("%d%d",&x,&y);

data[x][y] = 1;

}

memset(dp,-1,sizeof(dp));

printf("%d\n",solve(0,0));

return 0;

}