首页 > 代码库 > 2014.12.14

2014.12.14

挑战编程程序设计 搜索练习

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;    }}
莫名dp

 

2014.12.14