SRM501 Div2 Hard

1000
メモ化する。
memo[長さ][これまでの合計][最後に使った数][何連続で減少しているか];

view plainprint?

1. const lli mod = 1000000007;  
2.   
3. const int LEN = 40 + 1;  
4. const int SUM = 40 * 40 + 1;  
5. const int N = 40 + 1;  
6.   
7. lli memo[LEN][SUM][N][2];  
8.   
9. lli rec(int len, int sum, int last, int cons, const vector<int> &v)  
10. {  
11.   if (cons == 2) return 0;  
12.   if (v.size() == len) return 1;  
13.   
14.   lli &ret = memo[len][sum][last][cons];  
15.   if (ret != -1) return ret;  
16.   
17.   lli total = 0;  
18.   
19.   for (int n = 0; n < N; ++n) {  
20.     if (v[len] == -1 || v[len] == n) ; else continue;  
21.     if (n * len <= sum) {  
22.       total += rec(len + 1, sum + n, n, (n < last) ? cons + 1 : 0, v);  
23.       total %= mod;  
24.     }  
25.   }  
26.   
27.   return ret = total;  
28. }  
29.   
30. class FoxAverageSequence {  
31. public:  
32.   int theCount(vector <int> seq)  
33.   {  
34.     fill(&memo[0][0][0][0], &memo[LEN - 1][SUM - 1][N - 1][2], -1);  
35.     return rec(0, 0, 0, 0, seq);  
36.   }  
37. };  

const lli mod = 1000000007;

const int LEN = 40 + 1;
const int SUM = 40 * 40 + 1;
const int N = 40 + 1;

lli memo[LEN][SUM][N][2];

lli rec(int len, int sum, int last, int cons, const vector<int> &v)
{
  if (cons == 2) return 0;
  if (v.size() == len) return 1;

  lli &ret = memo[len][sum][last][cons];
  if (ret != -1) return ret;

  lli total = 0;

  for (int n = 0; n < N; ++n) {
    if (v[len] == -1 || v[len] == n) ; else continue;
    if (n * len <= sum) {
      total += rec(len + 1, sum + n, n, (n < last) ? cons + 1 : 0, v);
      total %= mod;
    }
  }

  return ret = total;
}

class FoxAverageSequence {
public:
  int theCount(vector <int> seq)
  {
    fill(&memo[0][0][0][0], &memo[LEN - 1][SUM - 1][N - 1][2], -1);
    return rec(0, 0, 0, 0, seq);
  }
};