SRM395 div1 medium
一番高いビルから入れていく。
一番左に入れると左から見えるビルが一つ増える。
一番右に入れると右から見えるビルが一つ増える。
それ以外の場所に入れても見えるビルは増えない。
#include <cstdio> #include <cstring> using namespace std; typedef long long LL; LL cache[100+10][100+10][100+10]; class Skyscrapers { public: int N; LL rec(int left,int right,int pos) { if(0<=left && 0<=right) { LL &r=cache[left][right][pos]; if(r!=-1) return r; else if(pos==N) r=(left==0 && right==0)?1:0; else if(pos==0) r=rec(left-1,right-1,pos+1); else r=(rec(left-1,right,pos+1)+(pos-1)*rec(left,right,pos+1)+rec(left,right-1,pos+1))%1000000007; return r; } else return 0; } int buildingCount(int _N, int leftSide, int rightSide) { N=_N; memset(cache,-1,sizeof(cache)); return rec(leftSide,rightSide,0); } };