题目大意：
有一组n个不相同的数字组成数串：a1,a2,a3…an。
1.一个数组b。
2.第一个操作我们将b0的值赋为a1。之后我们有n-1个操作，第k次操作我们将by=bi+bj（y,i,j可能相同）。
3.每次操作结束后我们依次取出by。按顺序组成新串。
问操作结束后，我们获得的新串能否与a数串相同。如果可以输出数组b所需的最小长度。反之输出-1。
思路：
先介绍一个纯dfs的算法：每次依次枚举i,j,y，然而会T。
不过，可以发现，b中的数必定在a中出现过。因此，记忆化搜索，状态（s）中存的是a1到an是否在b中，则s中1的个数即为b的长度。之后进行dfs，当然每种状态只需搜到一次。
记住：by,bi,bj可以在已有的b中任取！
有两种方式：
1.顺着，每次check一下第k个能否得到，之后dfs，但check复杂度较高。
2.倒着，从第n个数倒推，取子状态中最小的，再与当前的进行判断。
代码：
顺着：
1 #include<cstdio> 2 int n,i,ans,a[25],mi[25]; 3 bool vis[1<<23]; 4 5 bool check(int s,int k) 6 { 7 for (int i=0;i<n;++i) 8 for (int j=i;j<n;++j) 9 if ((mi[i]&s) && (mi[j]&s) && (a[i]+a[j]==a[k])) return 0; 10 return 1; 11 } 12 13 void dfs(int k,int s)//s Status 14 { 15 if (vis[s]) return; 16 int i,cnt=0; vis[s]=1; 17 for (i=s;i;i=i>>1) cnt=cnt+(i&1); 18 if (ans<=cnt) return; 19 if (k==n) { ans=cnt; return; } 20 if (check(s,k)) return; 21 dfs(k+1,s|mi[k]); 22 for (i=0;i<n;++i) 23 if (s&mi[i]) dfs(k+1,(s^mi[i])|mi[k]); 24 } 25 26 int main() 27 { 28 scanf("%d",&n); 29 for (i=0;i<n;++i) scanf("%d",&a[i]); 30 for (mi[0]=i=1;i<=n;++i) mi[i]=mi[i-1]<<1; 31 ans=30; dfs(1,1); printf("%d\n",ans<30?ans:-1); 32 return 0; 33 }倒着：
1 #include<cstdio> 2 const int M=24; 3 int n,i,a[M],mi[M],dp[1<<M]; 4 5 void dfs(int k,int s) 6 { 7 if (dp[s]) return; 8 dp[s]=M; int i,j,t; 9 for (i=0;i<k;++i) 10 for (j=i;j<k;++j) 11 if (a[i]+a[j]==a[k]) 12 { 13 t=(s-mi[k]) | mi[i] | mi[j] | mi[k-1]; 14 dfs(k-1,t); 15 if (dp[s]>dp[t]) dp[s]=dp[t]; 16 } 17 for (t=0,i=s;i;i=i>>1) t=t+(i&1); 18 if (dp[s]<t) dp[s]=t; 19 } 20 21 int main() 22 { 23 scanf("%d",&n); 24 for (mi[0]=i=1;i<=n;++i) mi[i]=mi[i-1]<<1; 25 for (i=0;i<n;++i) scanf("%d",&a[i]); 26 --n,dp[1]=1,dfs(n,mi[n]); 27 if (dp[mi[n]]==M) printf("-1\n"); 28 else printf("%d\n",dp[mi[n]]); 29 return 0; 30 }
转载于:https://www.cnblogs.com/HHshy/p/6013266.html
相关资源：JAVA上百实例源码以及开源项目