亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

POJ1416-Shredding Company

系統 1872 0

轉載請注明出處:優 YoU? http://user.qzone.qq.com/289065406/blog/1304031265

?

題目翻譯 :

公司現在要發明一種新的碎紙機,要求新的碎紙機能夠把紙條上的數字切成最接近而不超過 target 值。比如, target 的值是 50 ,而紙條上的數字是 12346 ,應該把數字切成四部分,分別是 1 2 34 6 。因為這樣所得到的和 43 (= 1 + 2 + 34 + 6) 是所有可能中最接近而不超過 50 的。(比如 1, 23, 4, 6 就不可以 , 因為它們的和不如 43 接近 50 ,而 12, 34, 6 也不可以,因為它們的和超過 50 了。碎紙還有以下三個要求:

1 、如果 target 的值等于紙條上的值,則不能切。
2
、如果沒有辦法把紙條上的數字切成小于 target ,則輸出 error 。如 target 1 而紙條上的數字是 123 ,則無論你如何切得到的和都比 1 大。
3
、如果有超過一種以上的切法得到最佳值,則輸出 rejected 。如 target 15 ,紙條上的數字是 111 ,則有以下兩種切法 11 1 或者 1 11.
你的任務是編寫程序對數字進行劃分以達到最佳值。

?

解題思路:
DFS 深搜

(1) 比如一個 6 位數 n ,切成為 6 個數的話,這 6 個數的和如果大于目標數 aim 則不用再搜索了,因為這肯定是所有劃分中和最小的,而最小都比目標數大,自然就沒有合要求的答案了 .
(2)
如何切分,假如以 50 ? 12346 為例。
第一步,先切下一個 1” ,然后遞歸去切 2346”
第二步,再切下一個 12” ,然后遞歸去切 346”
第三步,再切下一個 123” ,然后遞歸去切 46”
第四步,再切下一個 1234” 然后遞歸去切 6”
第五步,再切下 12346”

(3) 切下來的 前面的數字串部分 則加入到劃分的和,剩下的部分繼續遞歸,直到剩下的數字串長度為 0 可以用一個 int 記錄劃分方式 (int p) 如上例的輸入為 50 ? 12346 時,其結果為 43 ? 1 ? 2 ? 34 ? 6 ,那么 p=1121 ,代表把 12346 劃分為 4 部分,第一部分為第 1 位,第二部分為第 2 位,第三部分為第 3 4 位,第四部分為第 5

(4) 注意在搜索時,必須把 n 剩余數字部分 轉化為字符串再搜索,不然若 剩余的數字開頭第一位為 0 時,會導致出錯。

(5) 剪枝方法:在搜索時若發現部分和 大于(不能等于) aim 時,則可結束搜索。

(6)error 的判定要在搜索前進行, rejected (多個最優解)的判定要在搜索后判定。

(7) 關于出現相同最優解的標記,每出每種劃分的 sum 每出現一次標記 +1 ,要使標記為 O(1) ,只需把 vist 數組開得足夠大。 N 最多為 6 位數,因此 Maxsum=999999

?

?

簡單的附上一個關于例 50 ? 12346 的不完全搜索樹

省略號為未列出的結點

POJ1416-Shredding Company

      
          1
      
      
        //
      
      
        Memory Time
        
2 // 4160K 157MS
3
4 #include < iostream >
5 #include < cmath >
6 #include < string >
7 using namespace std;
8
9 int getlen( int n) // 得到n的位長度
10 {
11 if (n < 10 )
12 return 1 ;
13 else if (n < 100 )
14 return 2 ;
15 else if (n < 1000 )
16 return 3 ;
17 else if (n < 10000 )
18 return 4 ;
19 else if (n < 100000 )
20 return 5 ;
21 else
22 return 6 ;
23 }
24
25 int getvalue( char * s, int i) // 得到數字字符串s前i位字符(數字)組成的int值
26 {
27 int k = i;
28 int sum = 0 ;
29 while (k)
30 {
31 k -- ;
32 sum += (s[k] - ' 0 ' ) * ( int )pow( 10.0 ,( double )(i - k - 1 ));
33 }
34 return sum;
35 }
36
37 int gethead( int n, int i) // 得到由n的前i位數字構成的int
38 {
39 int len = getlen(n);
40 if (len <= i)
41 return n;
42 return n / ( int )pow( 10.0 ,( double )(len - i));
43 }
44
45 int gettail( int n, int i) // 得到由n的后i位數字構成的int
46 {
47 return n % ( int )pow( 10.0 ,( double )i);
48 }
49
50 int aim; // 目標數
51
52 int result; // 最優劃分的和
53 int path; // 最優劃分的劃分方式
54
55 int sum; // 某種劃分的和
56 int p; // 某種劃分方式
57
58 int vist[ 1000000 ]; // 記錄每個sum出現的次數
59 // 999999是當n=999999時的最大和值
60
61 void DFS( char * s, int len)
62 {
63 if (len == 0 )
64 {
65 vist[sum] ++ ;
66 if (sum > result && sum <= aim)
67 {
68 result = sum;
69 path = p;
70 }
71 return ;
72 }
73
74 for ( int i = 1 ;i <= len;i ++ )
75 {
76 int a = getvalue(s,i); // n的前i位字符轉變為數字留下,計入部分和
77 sum += a; // 部分和
78 if (sum > aim) // 剪枝,部分和已經大于aim,無需繼續往下搜索
79 {
80 sum -= a;
81 continue ;
82 }
83 p = p * 10 + i; // 記錄劃分方式
84
85 char b[ 7 ]; // 構造n的后i位字符序列,繼續遞歸
86 int j = 0 ;
87 for ( int k = i;k < len;k ++ )
88 b[j ++ ] = s[k];
89 b[j] = ' \0 ' ;
90
91 DFS(b,len - i);
92
93 sum -= a; // 回溯
94 p /= 10 ;
95 }
96 return ;
97 }
98
99 int main( void )
100 {
101 while ( true )
102 {
103 /* Input */
104
105 char s[ 7 ]; // 打印紙上的數字
106 cin >> aim >> s;
107
108 int len = strlen(s);
109 int n = getvalue(s,len); // 構造s的數字序列n
110
111 if ( ! aim && ! n)
112 break ;
113
114 if (aim == n) // 目標值與打印紙上的數字一致
115 {
116 cout << aim << ' ' << n << endl;
117 continue ;
118 }
119
120 int num = n; // temporary
121 int k = 0 ; // n的各位數字之和
122 while (num)
123 {
124 k += num % 10 ; // 逐位劃分是 和最小的劃分方式
125 num /= 10 ;
126 }
127 if (k > aim) // 最小和也大于aim,則所有劃分都大于aim
128 {
129 cout << " error " << endl;
130 continue ;
131 }
132
133 /* Initial */
134
135 result =- 1 ;
136 sum = 0 ;
137 path = 0 ;
138 p = 0 ;
139 memset(vist, 0 , sizeof (vist));
140
141 /* DFS */
142
143 DFS(s,len);
144
145 /* Output */
146
147 if (vist[result] > 1 ) // 最優解多于一個
148 cout << " rejected " << endl;
149 else if (vist[result] == 1 ) // 有唯一最優解
150 {
151 cout << result << ' ' ;
152
153 int L = getlen(path); // 輸出劃分的方式
154 for ( int i = 1 ;i <= L;i ++ )
155 {
156 int k = gethead(path, 1 ); // 取path的第一位k,k的值等于n的第一段劃分位數,即從n的第1位到第k位
157 cout << gethead(n,k) << ' ' ;
158 n = gettail(n,len -= k);
159 path = gettail(path,L - i);
160 }
161 cout << endl;
162 }
163 }
164 return 0 ;
165 }

POJ1416-Shredding Company


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 在线观看 中文字幕 | 色综合久久久久久中文网 | 黄色伊人网 | 久久精品视频亚洲 | 男人的天堂在线免费视频 | 四虎最新永久免费视频 | 456性欧美欧美在线视频 | 99久女女精品视频在线观看 | 日日爽| 99热这里只有精品3 99热这里只有精品4 | 中文字幕在线视频免费观看 | 宅男在线影院 | 一级女人18片毛片免费视频 | 免费观看欧美一级高清 | 色婷婷网 | 亚洲精品高清在线一区二区三区 | 一及黄色毛片 | 91视频中文字幕 | 一区二区日本 | 伊人久热这里只精品视频 | 日韩精品一区二区三区毛片 | 欧美综合社区 | 亚洲爱v| 国产成人亚洲精品77 | 91精品乱码一区二区三区 | 一级片免费在线 | 国产不卡影院 | 欧美成人另类 | 九九操| 手机看片一区二区 | 亚洲欧美一区二区三区在线 | 97在线视频免费观看 | 大学生久久香蕉国产线看观看 | 国产一级一片免费播放 | 精品视频在线免费观看 | 亚洲国产成人久久综合一 | 色噜噜五月综合激情久久爱 | 四虎在线观看视频 | 亚欧精品一区二区三区四区 | 精品成人免费一区二区在线播放 | 五月婷婷一区 |