SRM 653 Div1 250 : CountryGroupHard

[備忘録]
問題概要 :
備忘録なので略

解法 :
DP
{ 0, 0, 3, 3, 0, 0 } という数列が与えられたとする
0..1...2...3...4...5...6

0

0

3

3

0

0

みたいな感じで間に板を置き、左から昇順に番号を割り振る

dp[i] := 0番の板からi番の板までで条件を満たす組み合わせの数　とする
dp[0] = 1

コード :

typedef long long ll;
const int IINF = INT_MAX;
const string YES = "Sufficient";
const string NO  = "Insufficient";

ll dp[1000];

class CountryGroupHard {
public:
  string solve( vector<int> arr ) {
    dp[0] = 1;
    REP(i,1,arr.size()+1) {
      REP(j,1,i+1){
        bool success = true;
        rep(k,j) if( arr[i-1-k] && arr[i-1-k] != j ) { success = false; break; }
        if( success ) dp[i] += dp[i-j];
     }
    }
    return ( dp[arr.size()] == 1LL ) ? YES : NO;
  }
};