백준 2240번 자두나무 ( C++ )

문제

https://www.acmicpc.net/problem/2240

 

해설

경우의수가 너무 커서 dp로 해결

-1로 초기화 할 경우 ~ret을 사용하면 -1일때만 false를 반환하도록할 수 있음

 

코드

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
int t,w,dp[1004][2][34], mv[1004];
 
int go(int idx, int location, int cnt){
  if(cnt < 0) return -10000;
  if(idx >= t) return 0;
  int &ret = dp[idx][location][cnt];
  if(~ret) return ret;
  return ret = max(go(idx+1,location,cnt),go(idx+1,1^location,cnt-1)) +  ((location + 1) == mv[idx] ? 1 : 0);
}
 
int main(){
  cin >> t >> w;
  for(int i=0;i<t;i++){
    cin >> mv[i];
  }
  memset(dp,-1,sizeof(dp));
 
  cout << max(go(0,0,w),go(0,1,w-1));
}