正解是狀態壓縮的搜索
dfs求是否有可行解，bfs求最優解
[cpp
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
int n;
int num[2000],num1[2000];
int dp[1100][1100];
int dfs(int pos,int sta){
int npos,nsta,i,j,cou;
if(pos==n+1)return 1;
if(dp[pos][sta]!=-1)return dp[pos][sta];
int k=1;
for(i=1;i<10 && i+pos<=n && k<=5;i++){
if(((1<<i)&sta)==0)continue;
k++;
if(num[pos]==num[i+pos]){
for(j=1;j<10 && j+pos<=n;j++)
if(j!=i && ((1<<j)&sta))break;
if(j+pos==n+1 || j==10){
npos=pos+j;
nsta=(1<<10)-1;
dp[npos][nsta]=dfs(npos,nsta);
if(dp[npos][nsta]==1)
return 1;
}
else{
npos=pos+j;
nsta=sta>>j;
if(j<i)
nsta-=(1<<(i-j));
for(cou=10-j;cou<10;cou++)
nsta+=1<<cou;
dp[npos][nsta]=dfs(npos,nsta);
if(dp[npos][nsta]==1)
return 1;
}
}
}
dp[pos][sta]=0;
return 0;
}
int main(){
int i;
map<int,int>mp;
while(scanf("%d",&n)==1){
mp.clear();
for(i=1;i<=n;i++){
scanf("%d",&num1[i]);
if(mp.find(num1[i])!=mp.end())
mp[num1[i]]++;
else
mp[num1[i]]=1;
}
for(i=1;i<=n;i++)
num[i]=num1[n-i+1];
int flag=1;
for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){
if((it->second)%2){
flag=0;
break;
}
}
if(flag==0){
printf("0\n");
continue;
}
memset(dp,-1,sizeof(dp));
if(dfs(1,1023))
printf("1\n");
else
printf("0\n");
}
}
