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]