正解是状态压缩的搜索
dfs求是否有可行解，bfs求最优解 [cpp #include #include #include #include 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< k++; if(num[pos]==num[i+pos]){ for(j=1;j<10 && j+pos<=n;j++) if(j!=i && ((1< 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 nsta-=(1<<(i-j)); for(cou=10-j;cou<10;cou++) nsta+=1< dp[npos][nsta]=dfs(npos,nsta); if(dp[npos][nsta]==1) return 1; } } } dp[pos][sta]=0; return 0; } int main(){ int i; mapmp; 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::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"); } }