SRM653 div1 easy CountryGroupHard

考えたこと

• dp[i] = (i番目までで終わるパターン数)
• dp[i] = sum(dp[j]) (j<i, (j, i]が全員同じ国の条件を満たす) みたいな遷移をすればよさそう
• (j, i]が条件を満たすのは質問に答えた人がいない or 質問に答えた人が全員同じ人数でi-jと等しいとき
• dp[n-1] = 1 なら確定できるのでsufficient

DP遷移で頭爆発して実装に手間取った、むずかしい

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int dp[105];
class CountryGroupHard {
   public:
   string solve(vector <int> a)
  {
    memset(dp, 0, sizeof(dp));
    int n = a.size();
    int firstnum = -1;
    REP(i, n) {
      if(firstnum == -1 && a[i] != 0) firstnum = a[i];
      int cnt = 1, num = a[i];
      for(int j=i-1; j>=0; --j) {
        if(num == 0 || num == cnt) dp[i] += dp[j];
        if((num != 0 && a[j] != 0 && num != a[j]) || (num != 0 && num <= cnt)) break;
        if(a[j] != 0) {
          if(num == 0) num = a[j];
        }
        cnt++;
      }
      if(i == firstnum-1 || firstnum == -1) dp[i]++;
    }
    if(dp[n-1] == 1) return "Sufficient";
    return "Insufficient";
  }
};