挑战编程程序设计 搜索练习
8.6.1棋盘上的象
题目大意：在n*n的棋盘上放象，每个象的对角线上不能有别的象，求总共的方案数。
思路：搜索，肯定超时。dp~~排列组合~~又不会，只能打表了，好凶残。直接a（放0头象竟然是1种方案）。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int d1[20]={0},d2[20]={0},n,k; long long ans; void work(int i,int j,int di) { int dd1,dd2,yu; if (di>k) { ++ans; return; } if (i>n||j>n) return; yu=(n-i)*n+n-j+1; if (yu<k-di+1) return; dd1=i-j+8;dd2=i+j; if (d1[dd1]==0&&d2[dd2]==0) { ++d1[dd1];++d2[dd2]; if (j==n) work(i+1,1,di+1); else work(i,j+1,di+1); --d1[dd1];--d2[dd2]; } if (j==n) work(i+1,1,di); else work(i,j+1,di); } int main() { while(scanf("%d%d",&n,&k)==2) { if (n==0&&k==0) break; ans=0; memset(d1,0,sizeof(d1)); memset(d2,0,sizeof(d2)); work(1,1,1); printf("%lld\n",ans); } }
#include<iostream> #include<cstdio> using namespace std; long long biao[9][65]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,9,26,26,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,16,92,232,260,112,16,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,25,240,1124,2728,3368,1960,440,32,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,36,520,3896,16428,39680,53744,38368,12944,1600,64,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,49,994,10894,70792,282248,692320,1022320,867328,389312,81184,5792,128,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,64,1736,26192,242856,1444928,5599888,14082528,22522960,22057472,12448832,3672448,489536,20224,256,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; int main() { int n,k; while(scanf("%d%d",&n,&k)==2) { if (n==0&&k==0) break; printf("%lld\n",biao[n][k]); } }
8.6.3队伍
题目大意：n个人站队，恰有p个人比左边的人都高，恰有r个人比右边的人都高，求总的方案数。
思路：搜索，一开始是按位置搜的，超时妥妥的。之后改了搜索方法，从高的往小的放，如果当前的人放在已放过的左边；就相当于多了一个比左边人都高的，如果当前的人放在已放过的右边，就相当于多了一个比右边人都高的；如果放在之间的话，就没有变化。然后搜出来的相对要快，可是还是没法满足我们的要求，于是又用了打表，打了十分钟的表，终于a了。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n; long long ans=0; bool use[14]={false}; void work(int i,int ll,int rr,int le,int re) { int j; if (i>n&&le==0&&re==0) { ++ans; return; } if (ll-1<le) return; if (n-rr<re) return; if (i==1) { for (j=le;j<=n-re+1;++j) { use[j]=true; work(i+1,j,j,le-1,re-1); use[j]=false; } } else { for (j=le;j<=n-re+1;++j) { if (j<1||j>n) continue; if (!use[j]) { use[j]=true; if (j<ll&&le>0) work(i+1,j,rr,le-1,re); if (j>ll&&j<rr) work(i+1,ll,rr,le,re); if (j>rr&&re>0) work(i+1,ll,j,le,re-1); use[j]=false; } } } } int main() { int i,j,ci,t,l,r; scanf("%d",&t); for (ci=1;ci<=t;++ci) { scanf("%d%d%d",&n,&l,&r); memset(use,false,sizeof(use)); ans=0; work(1,n+1,0,l,r); printf("%lld\n",ans); } }
#include<iostream> #include<cstdio> using namespace std; long long ans[14][14][14]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,2,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,1,0,0,0,0,0,0,0,0,0,0,2,6,3,0,0,0,0,0,0,0,0,0,0,0,3,3,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,6,11,6,1,0,0,0,0,0,0,0,0,0,6,22,18,4,0,0,0,0,0,0,0,0,0,0,11,18,6,0,0,0,0,0,0,0,0,0,0,0,6,4,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,24,50,35,10,1,0,0,0,0,0,0,0,0,24,100,105,40,5,0,0,0,0,0,0,0,0,0,50,105,60,10,0,0,0,0,0,0,0,0,0,0,35,40,10,0,0,0,0,0,0,0,0,0,0,0,10,5,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,120,274,225,85,15,1,0,0,0,0,0,0,0,120,548,675,340,75,6,0,0,0,0,0,0,0,0,274,675,510,150,15,0,0,0,0,0,0,0,0,0,225,340,150,20,0,0,0,0,0,0,0,0,0,0,85,75,15,0,0,0,0,0,0,0,0,0,0,0,15,6,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,720,1764,1624,735,175,21,1,0,0,0,0,0,0,720,3528,4872,2940,875,126,7,0,0,0,0,0,0,0,1764,4872,4410,1750,315,21,0,0,0,0,0,0,0,0,1624,2940,1750,420,35,0,0,0,0,0,0,0,0,0,735,875,315,35,0,0,0,0,0,0,0,0,0,0,175,126,21,0,0,0,0,0,0,0,0,0,0,0,21,7,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5040,13068,13132,6769,1960,322,28,1,0,0,0,0,0,5040,26136,39396,27076,9800,1932,196,8,0,0,0,0,0,0,13068,39396,40614,19600,4830,588,28,0,0,0,0,0,0,0,13132,27076,19600,6440,980,56,0,0,0,0,0,0,0,0,6769,9800,4830,980,70,0,0,0,0,0,0,0,0,0,1960,1932,588,56,0,0,0,0,0,0,0,0,0,0,322,196,28,0,0,0,0,0,0,0,0,0,0,0,28,8,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,40320,109584,118124,67284,22449,4536,546,36,1,0,0,0,0,40320,219168,354372,269136,112245,27216,3822,288,9,0,0,0,0,0,109584,354372,403704,224490,68040,11466,1008,36,0,0,0,0,0,0,118124,269136,224490,90720,19110,2016,84,0,0,0,0,0,0,0,67284,112245,68040,19110,2520,126,0,0,0,0,0,0,0,0,22449,27216,11466,2016,126,0,0,0,0,0,0,0,0,0,4536,3822,1008,84,0,0,0,0,0,0,0,0,0,0,546,288,36,0,0,0,0,0,0,0,0,0,0,0,36,9,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,362880,1026576,1172700,723680,269325,63273,9450,870,45,1,0,0,0,362880,2053152,3518100,2894720,1346625,379638,66150,6960,405,10,0,0,0,0,1026576,3518100,4342080,2693250,949095,198450,24360,1620,45,0,0,0,0,0,1172700,2894720,2693250,1265460,330750,48720,3780,120,0,0,0,0,0,0,723680,1346625,949095,330750,60900,5670,210,0,0,0,0,0,0,0,269325,379638,198450,48720,5670,252,0,0,0,0,0,0,0,0,63273,66150,24360,3780,210,0,0,0,0,0,0,0,0,0,9450,6960,1620,120,0,0,0,0,0,0,0,0,0,0,870,405,45,0,0,0,0,0,0,0,0,0,0,0,45,10,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3628800,10628640,12753576,8409500,3416930,902055,157773,18150,1320,55,1,0,0,3628800,21257280,38260728,33638000,17084650,5412330,1104411,145200,11880,550,11,0,0,0,10628640,38260728,50457000,34169300,13530825,3313233,508200,47520,2475,55,0,0,0,0,12753576,33638000,34169300,18041100,5522055,1016400,110880,6600,165,0,0,0,0,0,8409500,17084650,13530825,5522055,1270500,166320,11550,330,0,0,0,0,0,0,3416930,5412330,3313233,1016400,166320,13860,462,0,0,0,0,0,0,0,902055,1104411,508200,110880,11550,462,0,0,0,0,0,0,0,0,157773,145200,47520,6600,330,0,0,0,0,0,0,0,0,0,18150,11880,2475,165,0,0,0,0,0,0,0,0,0,0,1320,550,55,0,0,0,0,0,0,0,0,0,0,0,55,11,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,39916800,120543840,150917976,105258076,45995730,13339535,2637558,357423,32670,1925,66,1,0,39916800,241087680,452753928,421032304,229978650,80037210,18462906,2859384,294030,19250,726,12,0,0,120543840,452753928,631548456,459957300,200093025,55388718,10007844,1176120,86625,3630,66,0,0,0,150917976,421032304,459957300,266790700,92314530,20015688,2744280,231000,10890,220,0,0,0,0,105258076,229978650,200093025,92314530,25019610,4116420,404250,21780,495,0,0,0,0,0,45995730,80037210,55388718,20015688,4116420,485100,30492,792,0,0,0,0,0,0,13339535,18462906,10007844,2744280,404250,30492,924,0,0,0,0,0,0,0,2637558,2859384,1176120,231000,21780,792,0,0,0,0,0,0,0,0,357423,294030,86625,10890,495,0,0,0,0,0,0,0,0,0,32670,19250,3630,220,0,0,0,0,0,0,0,0,0,0,1925,726,66,0,0,0,0,0,0,0,0,0,0,0,66,12,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0}; int main() { int ci,n,l,r; scanf("%d",&ci); while(ci) { scanf("%d%d%d",&n,&l,&r); printf("%lld\n",ans[n][l][r]); --ci; } }
8.6.5拔河
题目大意：有n个人拔河，将这n个人尽量平分，使两队的人不相差多于1个，然后使两队的体重数相差尽量小，输出分配方案。
思路：之前做过这个题，用的是背包。用容积为总容积一半的背包，装一半的物品，然后用布尔数组保存这些，最后从一半容积处穷举，找到最优解就可以了。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; bool f[101][45001]={false}; int a[101]={0}; int main() { int i,j,sum=0,n,k,q,cha,summ,ci; scanf("%d",&ci); while(ci) { cin>>n; sum=0; memset(f,false,sizeof(f)); if (n%2==0) k=n/2; else k=n/2+1; for (i=1;i<=n;++i) { cin>>a[i]; sum+=a[i]; } if (sum%2==0) summ=sum/2; else summ=sum/2+1; for (i=0;i<=n;++i) f[i][0]=true; for (i=1;i<=n;++i) for (j=summ;j>=a[i];--j) for (q=k;q>=1;--q) f[q][j]=f[q][j]||f[q-1][j-a[i]]; for (j=summ;j>=0;--j) if (f[k][j]) { cout<<min(j,sum-j)<<" "<<max(j,sum-j)<<endl; break; } if (ci>1) cout<<endl; --ci; } }
原文：http://www.cnblogs.com/Rivendell/p/4162933.html
