SRM349 div1 medium

昇順にソートすると簡単になる。
rec(今何番目のサイコロ、最低でも出さなければいけない目)をメモ化。

#include <algorithm>
#include <cstring>
#include <vector>

typedef long long LL;
using namespace std;

class DiceGames 
{
	public:

		int n;
		LL cache[50][50];
		vector<int> sides;

		LL rec(int k,int least)
		{
			LL &r=cache[k][least];
			if(r!=-1)
				;
			else if(k==n)
				r=1;
			else
			{
				r=0;
				for(int i=least;i<=sides[k];i++)
					r+=rec(k+1,i);
			}
			return r;
		}

		LL countFormations(vector<int> _sides)
		{
			sides=_sides;
			n=sides.size();
			sort(sides.begin(),sides.end());

			memset(cache,-1,sizeof(cache));
			return rec(0,1);
		}
};