烏龜棋 NOIP2010復(fù)賽 提高組 試題二 解題代碼

1、烏龜棋 （NOIP2010）復(fù)賽 提高組 試題二 解題代碼 分類： C/C+ 解題代碼 2011-07-23 18:56 271人閱讀 評論(2) 收藏 舉報 view plaincopy to clipboardprint?1. /* 2. 全國信息學(xué)奧林匹克聯(lián)賽（NOIP2010）復(fù)賽 提高組 第二題 3. 【問題描述】 4. 小明過生日的時候，爸爸送給他一副烏龜棋當(dāng)作禮物。 5. 烏龜棋的棋盤是一行N 個格子，每個格子上一個分?jǐn)?shù)（非負(fù)整數(shù)）。棋盤第1 格是唯一 6. 的起點，第N 格是終點

2、，游戲要求玩家控制一個烏龜棋子從起點出發(fā)走到終點。 7.  8. 1 2 3 4 5  N 9. 烏龜棋中M 張爬行卡片，分成4 種不同的類型（M 張卡片中不一定包含所有4 種類型 10. 的卡片，見樣例），每種類型的卡片上分別標(biāo)有1、2、3、4 四個數(shù)字之一，表示使用這種卡 11. 片后，烏龜棋子將向前爬行相應(yīng)的格子數(shù)。游戲中，玩家每次需要從所有的爬行卡片中選擇 12. 一張之前沒有使用過的爬行卡片，控制烏龜棋子前進(jìn)相應(yīng)的格

3、子數(shù)，每張卡片只能使用一次。 13. 游戲中，烏龜棋子自動獲得起點格子的分?jǐn)?shù)，并且在后續(xù)的爬行中每到達(dá)一個格子，就得到 14. 該格子相應(yīng)的分?jǐn)?shù)。玩家最終游戲得分就是烏龜棋子從起點到終點過程中到過的所有格子的 15. 分?jǐn)?shù)總和。 16. 很明顯，用不同的爬行卡片使用順序會使得最終游戲的得分不同，小明想要找到一種卡 17. 片使用順序使得最終游戲得分最多。 18. 現(xiàn)在，告訴你棋盤上每個格子的分?jǐn)?shù)和所有的爬行卡片，你能告訴小明，他最多能得到 19. 多少分嗎？ 20. 【輸入】 21. 輸入文件名torto

4、ise.in。輸入文件的每行中兩個數(shù)之間用一個空格隔開。 22. 第1 行2 個正整數(shù)N 和M，分別表示棋盤格子數(shù)和爬行卡片數(shù)。 23. 第2 行N 個非負(fù)整數(shù)，a1, a2, , aN，其中ai 表示棋盤第i 個格子上的分?jǐn)?shù)。 24. 第3 行M 個整數(shù)，b1,b2, , bM，表示M 張爬行卡片上的數(shù)字。 25. 輸入數(shù)據(jù)保證到達(dá)終點時剛好用光M 張爬行卡片， 26. 即N?1=Mi

5、 b1。 27. 【輸出】 28. 輸出文件名tortoise.out。 29. 全國信息學(xué)奧林匹克聯(lián)賽（NOIP2010）復(fù)賽 提高組 30. 第 4 頁 共 7 頁 31. 輸出只有1 行，1 個整數(shù)，表示小明最多能得到的分?jǐn)?shù)。 32. 【輸入輸出樣例1】 33. tortoise.in tortoise.out 34. 9 5 35. 6 10 14 2

6、0;8 8 18 5 17 36. 1 3 1 2 1 37. 73 38. 【輸入輸出樣例 1 說明】 39. 小明使用爬行卡片順序為1，1，3，1，2，得到的分?jǐn)?shù)為6+10+14+8+18+17=73。注意， 40. 由于起點是1，所以自動獲得第1 格的分?jǐn)?shù)6。 41. 【輸入輸出樣例2】 42. tortoise.in tortoise.out 43. 13 8 44.

7、4 96 10 64 55 13 94 53 5 24 89 8 30 45. 1 1 1 1 1 2 4 1 46. 455 47. 【數(shù)據(jù)范圍】 48. 對于30%的數(shù)據(jù)有1  N 30，1 M 12。 49. 對于50%的數(shù)據(jù)有1  N 120，1 M 

8、50，且4 種爬行卡片，每種卡片的張數(shù)不會超 50. 過20。 51. 對于100%的數(shù)據(jù)有1  N 350，1 M 120，且4 種爬行卡片，每種卡片的張數(shù)不會 52. 超過40；0  ai  100，1  i  N；1  bi  4，1  i M。 53. 輸入數(shù)據(jù)保證N?1=Mi b1。 54.  55

9、. */  56.   57.   58. #include <stdio.h>   59. #include <stdlib.h>   60.   61. #define IN_FILE_NAME    "tortoise.in"   62. #define OUT_FILE_NAME   "

10、tortoise.out"   63.   64. int g_iBlockNum = 0,g_iCardCnt = 0;  65. int g_iScordOut = 0;  66. int g_BlockScord350,g_Card120;  67.   68. void ReadFile()  69.   70.

11、60;   int i = 0;  71.     FILE *fp = fopen(IN_FILE_NAME,"rb");  72.       73.     if (fp = NULL)  74.     

12、0; 75.         return;  76.       77.     fscanf(fp,"%d%d",&g_iBlockNum,&g_iCardCnt);  78.     for (i = 0;i < g_iBlockN

13、um;i+)  79.       80.         fscanf(fp,"%d",&g_BlockScordi);  81.       82.     for (i = 0;i < g_iCardCnt;i+) &#

14、160;83.       84.         fscanf(fp,"%d",&g_Cardi);  85.       86.     fclose(fp);  87.   88.   89.   90. void 

15、WriteFile()  91.   92.     int i = 0;  93.     FILE *fp = fopen(OUT_FILE_NAME,"wb");  94.     if (fp = NULL)  95.    

16、60;  96.         return;  97.       98.     fprintf(fp,"%d",g_iScordOut);  99.     fclose(fp);  100.   101.   102. void&

17、#160;InitNewCard(int *pCardOld,int *pCardNew,int iCardCnt,int iCardExcept)  103.   104.     /* 105.     *   功能： 把pCardOld的iCardCnt張卡片復(fù)制到pCardNew，但把 106.     *  

18、         第iCardExcept張卡片排除（實際復(fù)制iCardCnt - 1 張） 107.     */  108.     int j = 0;  109.     for(int i=0;i<iCardCnt;i+)  110.

19、       111.         if(iCardExcept != i)  112.           113.             pCardNewj = pCar

20、dOldi;  114.             j+;  115.           116.       117.   118.   119. int Play(int *pBlockScord,int 

21、*pCard,int iCardCnt)  120.   121.     /* 122.     *   功能： 從當(dāng)前為pBlockScord的格子中找到一種選卡方法，使得 123.     *           游戲得到最多的分?jǐn)?shù)，并返回這個分?jǐn)?shù)

22、60;124.     *   參數(shù): pBlockScord,指向格子數(shù)組指針 125.     *           pCard,指向卡片數(shù)組指針 126.     *           iC

23、ardCnt，剩余卡片數(shù)量 127.     *   實現(xiàn)： 主要是分治法，漢諾塔思想 128.     */  129.     int iMax = 0,iRet = 0;  130.     int iNumOfCard = pCard0;/卡片上的數(shù)字

24、   131.     int *pNewCard = NULL;  132.     if (iCardCnt = 1)  133.       134.         /遞歸出口，只有一張卡片時，自然只能得到腳下格子分?jǐn)?shù)及走一步   

25、135.         /格子的分?jǐn)?shù)   136.         return pBlockScordiNumOfCard+pBlockScord0;  137.       138.     for (int i=0;i<iCardCnt;i+) 

26、 139.       140.         pNewCard = new intiCardCnt;  141.         InitNewCard(pCard,pNewCard,iCardCnt,i);  142.       &

27、#160; /遞歸搜索   143.         /思想是，只要下一步能夠得到最大值，那么當(dāng)前返回的就是最大值   144.         iRet = Play(pBlockScord+pCardi,pNewCard,iCardCnt -1);  145.         if (iRet > iMax)  146.           147.