Topcoder SRM 653 Div1 250

Topcoder SRM 653 Div1 250

Problem

N個人坐成一排，屬於同一個公司的人都坐在一起（挨在一起），但不知道誰屬於哪個公司。現在問其中的某些人 他屬於哪個公司，他的回答是Ai，Ai=0表示此人未被詢問，否則表示他的回答。題目保證一定存在一種分組方案使得屬於同一公司的人都坐在一起。現問方案是否唯一？

Limits

TimeLimit(ms):2000

MemoryLimit(MB):256

N,Ai∈[1,100]

Solution

設dp[i]表示從i位置開始往後分組的情況，dp[i]=0表示無法分組，dp[i]=1表示可以分組且唯一，dp[i]=2表示可以分組且不唯一。顯然，i:N?1?>0，j:i+1?>N?1，此時分A[i]=0與A[i]≠0來dp。具體怎麼dp太麻煩，不講了。

Complexity

TimeComplexity:O(N2)

MemoryComplexity:O(N)

My Code

//Hello. I'm Peter.
#include
#include
#include
#include
#include
using namespace std;
#define gsize(a) (int)a.size()
#define clr(a) memset(a,0,sizeof(a))
#define rep(i, a, b) for (int i = a; i < b; i++)
#define dep(i, a, b) for (int i = a; i > b; i--)
#define repin(i, a, b) for (int i = a; i <= b; i++)
#define depin(i, a, b) for (int i = a; i >= b; i--)
#define N 101
int dp[N];
class CountryGroupHard{
public:
    string solve(vector  a){
        int len=gsize(a);
        clr(dp);
        depin(i,len-1,0){
            if(!a[i]){
                int p=-1;
                rep(j,i+1,len){
                    if(j==i+1) dp[i]=dp[j];
                    else if(dp[j]) dp[i]=2;
                    if(a[j]) p=j;
                    if(a[j]) break;
                }
                if(p==-1&&i==len-1) dp[i]=1;
                else if(p==-1) dp[i]=2;
                else if(a[p]>=p-i+1){
                    if(i+a[p]>len) continue;
                    bool ok=true;
                    rep(k,i,i+a[p]){
                        if(a[k]&&a[k]!=a[p]) ok=false;
                    }
                    if(!ok) continue;
                    if(i+a[p]==len) dp[i]=1;
                    else if(i+a[p]0
                if(i+a[i]>len) continue;
                bool ok=true;
                rep(k,i,i+a[i]){
                    if(a[k]&&a[k]!=a[i]) ok=false;
                }
                if(!ok) continue;
                if(i+a[i]==len) dp[i]=1;
                else if(i+a[i]