以下提供另外一個想法 #include <stdio.h> #define INTMAX 2147483647 int min(int a, int b){ return (a<b) ? a : b;} int main() { int D, a, b, c, A, B, C; int ncase; int i, j, k, ba, bb, bc, find; for( scanf("%d", &ncase); ncase>0; --ncase){ scanf("%d%d%d%d%d%d%d", &D, &a, &b, &c, &A, &B, &C); find = 0; ba = A>0 ? min(INTMAX/A, a) : a; for(i=0; i<=ba; ++i){ bb = B>0 ? min((INTMAX-i*A) / B, b) : b; for(j=0; j<=bb; ++j){ bc = C>0 ? min((INTMAX-i*A-j*B) / C, c) : c; for(k=0; k<=bc; ++k){ if(i*A + j*B + k*C == D){ find = 1; break; } } if(find == 1) break; } if(find == 1) break; } printf(find ? "yes\n" : "no\n"); } return 0; } chhsiao 助教提供的版本是一個一個數字往上加 再檢查有沒有加到溢位 這個版本之中則是直接先求出最多 A B C 可放幾個而不溢位 事先避免溢位發生 其中 ba bb bc 指的就是 A B C 使用個數的上限 INTMAX 定義的是 int 的上界 所以 INTMAX/A 即為最多可以放幾個 A 而不溢位 (注意這裡是整數除法！) (INTMAX-i*A)/B 即為放了 i 個 A 之後 還能放幾個 B 而不溢位 (INTMAX-i*A-j*B)/C 即為放了 i 個 A 和 j 個 B 之後 還能放幾個 C 而不溢位 其中用到的三元運算子 ?: 在助教課的時候有說 是一種很像 if 的運算子 (cond) ? (expr1) : (expr2) ; 的意思是指 (cond) 成立的時候回傳 expr1 否則回傳 expr2 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.53