NOIP复习(动态规划)

1、 NOIP复习第三章：动态规划分类： NOIP Wikioi ACM-ICPC/蓝桥杯/其他大学竞赛 动态规划2014-09-01 08:15 458人阅读 评论(0) 收藏 举报目录(?)+一、背包问题最基础的一类动规问题，相似之处在于给n个物品或无穷多物品或不同种类的物品，每种物品只有一个或若干个，给一个背包装入这些物品，要求在不超出背包容量的范围内，使得获得的价值或占用体积尽可能大，这一类题的动规方程fi一般表示剩余容量为i时取得的最大价值或最大占用体积，或者有多维状态，分别表示不同种物品的剩余量1

2、、Wikioi 1014 装箱问题题目描述 Description有一个箱子容量为V（正整数，0V20000），同时有n个物品（0n30），每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。输入描述 Input Description一个整数v，表示箱子容量一个整数n，表示有n个物品接下来n个整数，分别表示这n 个物品的各自体积输出描述 Output Description一个整数，表示箱子剩余空间。样例输入 Sample Input2468312797样例输出 Sample Output0一道

3、经典的背包动规，用数组f进行动规，fv=剩余容量为v时可以利用的最大体积，那么可以在每次输入一个物品体积cost时遍历剩余容量状态，当前状态的剩余容量为v时，可以选择装入物品(装入物品则当前状态可以利用的体积为fv-cost+cost)或不装入物品,推出动规方程:fv=maxfv-cost+costcpp view plaincopyprint?1. #include <stdio.h>  2. #include <string.h>  3.   4. #define M

4、AXN 30000  5.   6. int fMAXN; /fi=剩余体积为i时装入物品的最大体积  7.   8. int max(int a,int b)  9.   10.     if(a>b) return a;  11.     return b;  

5、;12.   13.   14. int main()  15.   16.     int v,n,cost;  17.     scanf("%d%d",&v,&n);  18.     for(int i=1;i<=n;i+)   19.  

6、     20.         scanf("%d",&cost);  21.         for(int j=v;j>=cost;j-)  22.             fj=

7、max(fj,fj-cost+cost);  23.       24.     printf("%dn",v-fv);  25.     return 0;  26.    2、Wikioi 1068 乌龟棋题目描述 Description小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。 乌龟棋的棋盘是一行N个格子，每个格子上

8、一个分数（非负整数）。棋盘第1格是唯一 的起点，第N格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。 1 2 3 4 5 N 乌龟棋中M张爬行卡片，分成4种不同的类型（M张卡片中不一定包含所有4种类型 的卡片，见样例），每种类型的卡片上分别标有1、2、3、4四个数字之一，表示使用这种卡 片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择 一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。 游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到 该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到

9、终点过程中到过的所有格子的 分数总和。 很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡 片使用顺序使得最终游戏得分最多。 现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到 多少分吗？输入描述 Input Description输入的每行中两个数之间用一个空格隔开。 第1行2个正整数N和M，分别表示棋盘格子数和爬行卡片数。 第2行N个非负整数，a1a2aN，其中ai表示棋盘第i个格子上的分数。 第3行M个整数，b1b2bM，表示M张爬行卡片上的数字。 输入数据保证到达终点时刚好用光M张爬行卡片，即N - 1=(1->M)

10、bi输出描述 Output Description输出一行一个整数样例输入 Sample Input13 84 96 10 64 55 13 94 53 5 24 89 8 301 1 1 1 1 2 4 1样例输出 Sample Output455数据范围及提示 Data Size & Hint【数据范围】对于30%的数据有1  

11、;N 30，1 M 12。对于50%的数据有1  N 120，1 M 50，且4 种爬行卡片，每种卡片的张数不会超过20。对于100%的数据有1  N 350，1 M 120，且4 种爬行卡片，每种卡片的张数不会超过40；0  ai  100，1  i  N；1  bi  4，1  i M。输入数据

12、保证N1=Mi b1可以说这是一道背包的变形题，不再是只有单一的状态(剩余体积)，实际上因为卡片分种类，导致状态变成了4个：4种爬行卡片分别剩余的张数，则可用数组f来进行动规，fijkh=1、2、3、4号卡片各用掉i,j,k,h张时，下棋获得的最大分数，则每次从小到大动规，经过状态fijkh时，考虑用掉一张1或2或3或4号卡片，那么这次操作之前得到的分数就是fi-1kjh或fik-1jh或fikj-1h或fikjh-1(注：上次操作得到的分数并不包含上次操作后到达的格子分数)，然后再加上上次操作后到达的格子分数，这次操作到达的格子分数就等到下次操作时再算。最后输出fcard1card

13、2card3card4+mapn,cardx=第x种卡片的张数，mapn=终点的分数。当然也可以先算上起点的格子分数，每次决策时不加上次操作到达的格子分数，而是加上本次操作到达的格子分数，或许更便于理解cpp view plaincopyprint?1. #include <stdio.h>  2. #include <string.h>  3.   4. #define MAXM 40  5. #define MAXN 

14、400  6.   7. int fMAXMMAXMMAXMMAXM; /fijkh=1 2 3 4四种卡片各用了i,j,k,h张时的最高分数  8. int mapMAXN; /棋盘上的分数  9.   10. int max(int a,int b)  11.   12.     if(a>b) r

15、eturn a;  13.     return b;  14.   15.   16. int main()  17.   18.     int n,m;  19.     int card5=0;  20.     scan

16、f("%d%d",&n,&m);  21.     for(int i=1;i<=n;i+)  22.         scanf("%d",&mapi);  23.     for(int i=0;i<m;i+)  24.    &

17、#160;  25.         int kind;  26.         scanf("%d",&kind);  27.         cardkind+;  28.      &

18、#160;29.     for(int i=0;i<=card1;i+)  30.         for(int j=0;j<=card2;j+)  31.             for(int k=0;k<=card3;k+)  32.

19、60;               for(int h=0;h<=card4;h+)  33.                   34.         

20、;            int dis=i*1+j*2+k*3+h*4; /dis=当前用了i,j,k,h张牌后乌龟棋移动的距离  35.                     if(i>=1) fijkh=max(fi

21、jkh,fi-1jkh+map1+(i-1)*1+j*2+k*3+h*4);  36.                     if(j>=1) fijkh=max(fijkh,fij-1kh+map1+i*1+(j-1)*2+k*3+h*4);  37.        &

22、#160;            if(k>=1) fijkh=max(fijkh,fijk-1h+map1+i*1+j*2+(k-1)*3+h*4);  38.                     if(h>=1) fij

23、kh=max(fijkh,fijkh-1+map1+i*1+j*2+k*3+(h-1)*4);  39.                   40.     printf("%dn",fcard1card2card3card4+mapn);  41.     return

24、0;0;  42.   3、POJ 1276 Cash Machine(多重背包经典题)/problem?id=1276题目大意：要用n种钱币凑面额cash，要取凑到的面额必须小于等于Cash，给定每种钱币的面值和张数，求最多能凑到的面额。经典的多重背包题，可以将每种钱币当成物品，钱币的体积和价值均为它的面值。cpp view plaincopyprint?1. #include <iostream>  2. #include <stdio.h> 

25、; 3. #include <string.h>  4. #include <stdlib.h>  5.   6. #define MAXN 11  7. #define MAXV 100010  8.   9. using namespace std;  10.   11. struct Thing &

26、#160;12.   13.     int n,v,w; /n件，价值为v，体积为w，在这个题中v=w  14. thingsMAXN;/保存每种纸币个数  15.   16. bool canGetMAXV; /canGeti=true表示面额i可以被取到  17.   18. int main()  19.   20.   

27、;  int cash,n;  21.     while(scanf("%d%d",&cash,&n)!=EOF)  22.       23.         int i,j,ans=0; /要取的面额为cash,n种钱币  24.    

28、     for(int i=1;i<=n;i+)  25.           26.             scanf("%d%d",&thingsi.n,&thingsi.v);  27.    &#

29、160;        thingsi.w=thingsi.v;  28.           29.         if(!cash|!n)  30.           31.  &#

30、160;          printf("0n");  32.             continue;  33.           34.       

31、  memset(canGet,false,sizeof(canGet);  35.         canGet0=true; /面额为0当然可以取到  36.         for(i=1,ans=0;i<=n;i+) /正在取第i种钱币  37.       

32、60;     for(j=ans;j>=0;j-) /取到的面额为j  38.                 if(canGetj) /面额j可以取到  39.              &

33、#160;      for(int k=1;k<=thingsi.n;k+) /第i种物品取n个  40.                       41.          &#

34、160;              int temp=j+k*thingsi.w;  42.                         if(temp>cash) /取

35、的面额超过了cash,太多了  43.                             break;  44.              &#

36、160;          canGettemp=true;  45.                         if(temp>ans) ans=temp;  46.   &#

37、160;                   47.         cout<<ans<<endl;  48.       49.     return 0; &#

38、160;50.   4、POJ 1742 Coins（带优化的多重背包）/problem?id=1742楼教主的经典题，题目大意是要用多种钱币凑出一个面额，这个面额小于等于v，给出每种钱币的面值和个数，求最终能凑出多少种面额cpp view plaincopyprint?1. #include <iostream>  2. #include <stdio.h>  3. #include <string.h>  4.

39、 #include <stdlib.h>  5. #include <algorithm>  6.   7. #define MAXN 110  8. #define MAXV 100100  9.   10. using namespace std;  11.   12. struct Thing  1

40、3.   14.     int n,v,w; /个数为n，价值为v，体积为w  15. coinsMAXN;  16.   17. bool canGetMAXV; /canGeti=true表示面额i可以被取到  18. int n,v;  19.   20. void ZeroOnePack(int cost) /01背包 

41、; 21.   22.     for(int i=v;i>=cost;i-)  23.         canGeti|=canGeti-cost;  24.   25.   26. void CompletePack(int cost) /完全背包  27.   28. 

42、0;   for(int i=cost;i<=v;i+)  29.         canGeti|=canGeti-cost;  30.   31.   32. void MultiplePack(int cost,int amount) /多重背包  33.   34.    &

43、#160;if(cost*amount>=v)  35.       36.         CompletePack(cost); /转换为完全背包问题  37.         return;  38.       39.  &#

44、160;  int k=1; /拿k件同样的物品  40.     while(k<amount)  41.       42.         ZeroOnePack(k*cost);  43.         amount-=k;

45、  44.         k<<=1; /k<-k*2  45.       46.     ZeroOnePack(amount*cost);  47.   48.   49. int main()  50.   51.  &#

46、160;  while(scanf("%d%d",&n,&v)  52.       53.         int ans=0;  54.         if(!n|!v) break;  55.    

47、60;    for(int i=1;i<=n;i+) scanf("%d",&coinsi.w);  56.         for(int i=1;i<=n;i+) scanf("%d",&coinsi.n);  57.         memse

48、t(canGet,false,sizeof(canGet);  58.         canGet0=true;  59.         for(int i=1;i<=n;i+) /当前正在尝试凑的硬币为第i个硬币  60.           &#

49、160; if(coinsi.n) /这个硬币有剩余  61.                 MultiplePack(coinsi.w,coinsi.n);  62.         for(int i=1;i<=v;i+) /面额为i  63. &

50、#160;           if(canGeti) /面额为i的可以取到  64.                 ans+;  65.         cout<<ans<&l

51、t;endl;  66.       67.     return 0;  68.   二、区间型动态规划这一类题目的相似之处在于动规方程fi表示以i结尾的价值/数量等等的大小，在决策时寻找i之前的位置j，使得fi取得最值3、Wikioi 1044 拦截导弹题目描述 Description    某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹

52、能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。  输入描述 Input Description输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）  输出描述 Output Description输出这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。样例输入 Sample Input389 207 155 300 299 170 158 65 样例输

53、出 Sample Output62数据范围及提示 Data Size & Hint导弹的高度<=30000，导弹个数<=20可以把导弹的高度化为一个数字序列，由题意可知，一个导弹拦截的目标必为原序列的不上升子序列，要想让拦截目标个数尽量多，就要求这个不上升子序列是最长的，换句话说，第一问就是求不上升子序列，第二问略微麻烦点，要让所有目标都被打而且导弹尽量少，那么需要每个导弹不光打一个目标，而且要把以这个目标为头的不上升子序列都打到，如图，绿色的线就是不上升子序列，红色的线是严格上升子序列，很明显，第二问要求最长严格上升子序列，这个子序列中的所有元素都需要

54、一发导弹，而它们连接的不上升子序列都能被这些导弹打到，第二问的答案就是最长严格上升子序列。cpp view plaincopyprint?1. #include <stdio.h>  2. #include <string.h>  3. #include <stdlib.h>  4.   5. #define MAXN 1000  6.   7. int upMAXN,d

55、nMAXN;  8. int highMAXN,cnt=0;  9. int maxDN=-1,maxUP=-1;  10.   11. int max(int a,int b)  12.   13.     if(a>b) return a;  14.     return b; 

56、 15.   16.   17. int main()  18.   19.     while(scanf("%d",&high+cnt)!=EOF);  20.     for(int i=1;i<=cnt;i+)  21.         for(i

57、nt j=1;j<i;j+)  22.           23.             if(highi>highj)  24.               25. 

58、0;               upi=max(upi,upj+1);  26.               27.             if(highi<=

59、highj)  28.               29.                 dni=max(dni,dnj+1);  30.           

60、;    31.           32.     for(int i=1;i<=cnt;i+)  33.       34.         maxDN=max(maxDN,dni);  35.   

61、      maxUP=max(maxUP,upi);  36.       37.     printf("%dn%dn",maxDN,maxUP+1);  38.     return 0;  39.   4、Wikioi 3027 线段覆盖2题目描述 Description

62、数轴上有n条线段，线段的两端都是整数坐标，坐标范围在01000000，每条线段有一个价值，请从n条线段中挑出若干条线段，使得这些线段两两不覆盖（端点可以重合）且线段价值之和最大。n<=1000输入描述 Input Description第一行一个整数n，表示有多少条线段。接下来n行每行三个整数, ai bi ci，分别代表第i条线段的左端点ai，右端点bi（保证左端点<右端点）和价值ci。输出描述 Output Description输出能够获得的最大价值样例输入 Sample Input31 2 12 3 21 3 4样例输出 Sample

63、 Output4数据范围及提示 Data Size & Hint数据范围对于40%的数据，n10；对于100%的数据，n1000；0<=ai,bi<=10000000<=ci<=1000000首先需要把所有线段根据右端点升序排序，这样的话，找与第i条线段不重合的线段j，就只需要往前找一个线段j，使得j的右端点小于等于i的左端点坐标，然后开一个数组f进行动规，数组fi=前i条线段，第i条线段必选，获得的最大价值，那么对于每一条线段i，在这条线段之前找一条不和它重合的线段j，使得fj+valuei取得最大值，DP方程为:fi=maxfj+valuei,j&

64、lt;i且线段i不与j重合  cpp view plaincopyprint?1. #include <stdio.h>  2. #include <string.h>  3. #include <algorithm>  4.   5. #define MAXN 1100  6.   7. using namespace std; 

65、 8.   9. struct Line  10.   11.     int L,R,w; /左端点，右端点，线段权值  12. lineMAXN;  13.   14. bool cmp(Line a,Line b)  15.   16.     return a.R<

66、b.R;  17.   18.   19. int fMAXN; /fi=前i条线段，第i条线段必选，获得的最大价值  20.   21. int main()  22.   23.     int n,ans=-1;  24.     scanf("%d",&n);  

67、25.     for(int i=1;i<=n;i+)  26.         scanf("%d%d%d",&linei.L,&linei.R,&linei.w);  27.     sort(line+1,line+n+1,cmp);  28.     for(int&#

68、160;i=1;i<=n;i+) fi=linei.w;  29.     for(int i=2;i<=n;i+)  30.       31.         for(int j=1;j<i;j+) /找到第i条线段之前的一条线段j,两条线段互不重合，这样就能把i插到j的后面  32.  

69、;           if(linei.L>=linej.R)  33.               34.                 fi=max(fi,

70、linei.w+fj);  35.               36.       37.     for(int i=1;i<=n;i+)  38.         ans=max(ans,fi); /找到了一个

71、结尾i，使得fi最大  39.     printf("%dn",ans);  40.     return 0;  41.   三、区间型动态规划这一类题的解法通常是开动规数组f(一般是两维)，fij表示区间i,j获得的最值，决策时寻找一个属于该区间的中点k，使fik+fk+1j取得最值，并用来更新fij5、Wikioi 石子合并题目描述 Description有n堆石子排成一列，每堆石子有一个

72、重量wi, 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和wi+wi+1。问安排怎样的合并顺序，能够使得总合并代价达到最小。输入描述 Input Description第一行一个整数n（n<=100）第二行n个整数w1,w2.wn  (wi <= 100)输出描述 Output Description一个整数表示最小合并代价样例输入 Sample Input44 1 1 4样例输出 Sample Output18数据范围及提示 Data Size & Hint这个题很明显是一个区间型动规，用fij

73、表示将区间i,j合并时的最小代价，则每次决策时寻找一个中点k，使得fik+fk+1j最小，并更新fij另外这个题需要注意一下，i是从大到小枚举的，我个人理解是：i从大到小枚举，最开始动规决策时需要的已求出的f就很少，否则刚开始决策时很多需要的f没有求出来，答案就会错误 cpp view plaincopyprint?1. #include <stdio.h>  2. #include <string.h>  3. #include <stdlib.h> 

74、60;4.   5. #define MAXN 1000  6. #define INF 10000000  7.   8. int fMAXNMAXN; /fij=合并区间i,j所获得的最大价值  9. int sumMAXN;  10.   11. int min(int a,int b)  12.   13. &

75、#160;   if(a<b) return a;  14.     return b;  15.   16.   17. int main()  18.   19.     int n;  20.     scanf("%d",&a

76、mp;n);  21.     for(int i=1;i<=n;i+)  22.       23.         int w;  24.         scanf("%d",&w);  25. &#

77、160;       sumi=sumi-1+w;  26.       27.     for(int i=n-1;i>=1;i-)  28.         for(int j=i+1;j<=n;j+)  29.    &#

78、160;      30.             int minAns=INF;  31.             for(int k=i;k<j;k+)  32.      

79、60;        33.                 minAns=min(minAns,fik+fk+1j+sumj-sumi-1);  34.               35. 

80、0;           fij=minAns;  36.           37.     printf("%dn",f1n);  38.     return 0;  39.   6、Wikio

81、i 1154 能量项链题目描述 Description在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m*r*n（Mars单位），新产生的珠子的头标记为m，尾标记为n。需要时，Mars人就用吸盘

82、夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号表示两颗珠子的聚合操作，(jk)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：(41)=10*2*3=60。这一串项链可以得到最优值的一个聚合顺序所释放的总能量为(41)2)3）=10*2*3+10*3*5+10*5*10=710。输入描述 Input Description第一行是一个

83、正整数N（4N100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1iN），当i<N< span>时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。输出描述 Output Description只有一行，是一个正整数E（E2.1*109），为一个最优聚合顺序所释放的总能量。样例输入 Sample Input42 3 5 1

84、0样例输出 Sample Output710这个题同样是区间型动态规划，和上一题很相似，最大的不同在于这个题的区间是一个环形的(没有起点和终点)，通常处理这种环形区间的问题，可以把有n个元素的环看作2*n长度的区间，n+1,2*n从1,n复制而来，这样就不存在区间终点该怎么和起点连接的问题，然后动规时需要先枚举一个合并区间的起点i，那么合并区间就是i,i+n-1，然后环形区间就转化成了一个直线区间，动规过程类似于上一题，时间复杂度O(n4)cpp view plaincopyprint?1. #include <stdio.h>  

85、2. #include <string.h>  3. #include <stdlib.h>  4.   5. #define MAXN 1000  6.   7. struct node  8.   9.     int head,tail;  10. ballMAXN;  11.  

86、; 12. int fMAXNMAXN; /fij=将i,j合并后获得的最大能量  13.   14. int max(int a,int b)  15.   16.     if(a>b) return a;  17.     return b;  18.   19.  

87、 20. int getEnergy(int m,int r,int n)  21.   22.     return ballm.head*ballr.tail*balln.tail;  23.   24.   25. int main()  26.   27.     int n; &

88、#160;28.     scanf("%d",&n);  29.     for(int i=1;i<=n;i+)  30.       31.         scanf("%d",&balli.head);  32.   

89、      balli-1.tail=balli.head;  33.       34.     balln.tail=ball1.head;  35.     for(int i=1;i<=n;i+)  36.         balli+

90、n=balli;  37.     for(int i=1;i<=n;i+) /start from position i,i,i+n-1  38.         for(int j=i+n-2;j>=i;j-)  39.           4

91、0.             for(int k=j+1;k<=i+n-1;k+)  41.               42.               

92、60; int maxAns=-1;  43.                 for(int p=j;p<k;p+)  44.                    

93、60;maxAns=max(maxAns,fjp+fp+1k+getEnergy(j,p,k);  45.                 fjk=maxAns;  46.               47.     &

94、#160;     48.     int maxAns=-1;  49.     for(int i=1;i<=n;i+)  50.         maxAns=max(maxAns,fii+n-1);  51.     printf("%dn&qu

95、ot;,maxAns);  52.     return 0;  53.   四、棋盘型动态规划个人认为这种动规是最简单的，因为它非常形象，很好推导出动规方程，这一类动规大多开二维动规数组，代表棋盘里每个坐标的状态7、Wikioi 1010 过河卒 题目描述 Description如图，A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例

96、如上图 C 点上的马可以控制 9 个点（图中的P1，P2 P8 和 C）。卒不能通过对方马的控制点。棋盘用坐标表示，A 点（0，0）、B 点（n,m）(n,m 为不超过 20 的整数，并由键盘输入)，同样马的位置坐标是需要给出的（约定: C不等于A，同时C不等于B）。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。1<=n,m<=15输入描述 Input Description键盘输入B点的坐标（n,m）以及对方马的坐标（X,Y）不用判错输出描述 Output Description屏幕输出一个整数（路径的条数）。样例输入 Sample In

97、put6 6 3 2样例输出 Sample Output17数据范围及提示 Data Size & Hint如描述这个题比较好做，只要在棋盘中标明所有马的控制点，动规时避开它们即可，fij表示经过(i,j)的路径条数，这个路径条数实际上就等于其左边的点和上方的点的路径条数之和，因为那两个点的路可以走到这个点，DP方程fij=fi-1j+fij-1,边界条件f00=1(左上角的点只可能有一条路经过)  cpp view plaincopyprint?1. #include <stdio.h>  2

98、. #include <string.h>  3. #include <stdlib.h>  4.   5. #define MAXN 100  6.   7. int mapMAXNMAXN;  8. int fMAXNMAXN;  9. int n,m;  10.   11. bool inMap(int

99、60;x,int y)  12.   13.     if(x<0|x>n|y<0|y>m) return false;  14.     return true;  15.   16.   17. int main()  18.   19.    

100、60;int x,y;  20.     scanf("%d%d%d%d",&n,&m,&x,&y);  21.     if(inMap(x,y) mapxy=1;  22.     if(inMap(x+2,y+1) mapx+2y+1=1;  23.     if(inM

101、ap(x+2,y-1) mapx+2y-1=1;  24.     if(inMap(x-2,y+1) mapx-2y+1=1;  25.     if(inMap(x-2,y-1) mapx-2y-1=1;  26.     if(inMap(x+1,y+2) mapx+1y+2=1;  27.     if(inM

102、ap(x+1,y-2) mapx+1y-2=1;  28.     if(inMap(x-1,y+2) mapx-1y+2=1;  29.     if(inMap(x-1,y-2) mapx-1y-2=1;  30.     f00=1;  31.     for(int i=0;i<=n;i+) &

103、#160;32.         for(int j=0;j<=m;j+)  33.             if(!mapij)  34.               35.   &

104、#160;             if(inMap(i-1,j) fij+=fi-1j;  36.                 if(inMap(i,j-1) fij+=fij-1;  37.         &