# d637: 路過的鴨duck 有一天,有一隻路過的鴨duck 牠…太餓結果就死了囧… 當他到天國的時候,遇到了先前駕崩的鴨子王(duck king), 牠變成了管理鴨子靈魂的神(duck king god,簡稱duckingod) duckingod生前是一隻非常聰明的神鴨, 所以duckingod給這隻路過的鴨一個復活的機會。 給牠一袋鴨飼料,裡面的每顆飼料有不同的體積和飽足感 只要路過的鴨能夠在有限的食量內吃得最飽, 那牠就能復活了! 快寫個程式幫幫路過的鴨吧!呱呱呱! 輸入說明 :每個測資點僅一組測資,不必EOF讀檔。 第一行有正整數n(1 #define N 10000 //飼料數 #define M 100 //胃容量(背包容量) using namespace std; long long int c[N+1][M+1], s[N], v[N]; //s[i]每顆飼料的體積,v[i]每個飼料的飽足感 int main() { int a, b, i, j, n; while (cin >> n ) { for (i=0; i<=N; i++) for (j=0; j<=M; j++) c[i][j]=0; for (i=1; i<=n; i++) cin >> s[i] >> v[i]; for (i=1; i<=n; i++) //對每一顆飼料考慮要不要吃 for (j=1; j<=M; j++) { //考慮空間大小 if (s[i]>j) c[i][j] = c[i-1][j]; //如果第i顆飼料體積太大,吃不下去,維持一樣的飽足感 else if (c[i-1][j] > c[i-1][j-s[i]] + v[i]) //還吃得下第i顆飼料 c[i][j]=c[i-1][j]; //如果沒有吃第i顆飼料的飽足感,比吃了第i顆飼料的飽足感還大, //那就不要吃了,飽足感維持一樣 else c[i][j]=c[i-1][j-v[i]] + v[i]; //如果吃了以後飽足感比較大,c[i][j]就設定成新的(較大的)飽足感 } cout << c[n][M] << endl; } return 0; } /********************************************************************/ /* Problem: d637 "路過的鴨duck" from jack1 */ /* Language: CPP (456 Bytes) */ /* Result: AC(4ms, 392KB) judge by this@ZeroJudge */ /* Author: pcmslouis at 2014-04-25 12:14:46 */ /********************************************************************/ // 一維解法 (目的減少浪費空間) #include #include using namespace std; int main() { int n, i, s, v, m; // n 飼料數, m 胃容量 int c[1000]={0}; scanf("%d",&n); while( n ) { scanf("%d %d", &s, &v); i=100; while( (i-s)>=0 ){ c[i] = max( c[i-s]+v , c[i] ); //吃了以後飽足感比較大,c[i]就設定成新的(較大的)飽足感 i--; } n--; } printf("%d\n",c[100]); return 0; } /**************************************************************************/ /* Problem: b131 "NOIP2006 2.开心的金明" from 2006 NOIP 普及組 */ /* Language: CPP (1010 Bytes) */ /* Result: AC(12ms, 5.4MB) judge by this@ZeroJudge */ /* Author: pcmslouis at 2013-02-22 10:30:00 */ /**************************************************************************/ // 二維解法 #include #define N 30000 #define M 25 using namespace std; long long int c[M][N], v[M+1], p[M+1]; int main() { int i, j, n, m; while (cin >> n >> m) { for (i=0; i<=m; i++) for (j=0; j<=n; j++) c[i][j]=0; for (i=1; i<=m; i++) cin >> v[i] >> p[i]; for (i=1; i<=m; i++) //對每一種物品考慮要不要買 for (j=1; j<=n; j++) { if (v[i]>j) c[i][j] = c[i-1][j]; //如果第i件物品太貴,買不起,就不買,維持一樣的乘積總和 else {//如果買得起第i件物品 if (c[i-1][j] > c[i-1][j-v[i]] + v[i]*p[i]) //如果沒有買第i件物品的乘積總和比買了第i件物品還大, c[i][j]=c[i-1][j]; //那就不要買了,乘積總和維持一樣 else c[i][j]=c[i-1][j-v[i]] + v[i]*p[i]; //如果買了第i件物品以後,乘積總和比較大, //c[i][j]就設定成新的(較大的)乘積總和 } } cout << c[m][n] << endl; } return 0; } /**************************************************************************/ /* Problem: b131 "NOIP2006 2.开心的金明" from 2006 NOIP 普及組 */ /* Language: CPP (537 Bytes) */ /* Result: AC(4ms, 768KB) judge by this@ZeroJudge */ /* Author: pcmslouis at 2014-04-28 17:59:11 */ /**************************************************************************/ // 一維解法 #include #include #define Z 30000 using namespace std; int main() { int i, n, m, v, p; // n 總錢數, m 物品個數, v 價格 , p 重要度 while ( cin >> n >> m) { int c[Z+1]={0}; // 重置所有1維數組值為0 while( m ) { cin >> v >> p; i=n; while( (i-v)>=0 ){ c[i] = max( c[i-v]+v*p , c[i] ); //選最大的 i--; } m--; } cout << c[n] << endl; } return 0; } /*******************************************************************/ /* Problem: b184 "5. 裝貨櫃問題" from 97高市資訊學科能力競賽 */ /* Language: CPP (457 Bytes) */ /* Result: AC(0ms, 332KB) judge by this@ZeroJudge */ /* Author: pcmslouis at 2014-03-06 16:35:55 */ /*******************************************************************/ // 一維解法 (目的減少浪費空間) #include #include #define M 100 // 貨櫃總容量 using namespace std; int main() { int i, n, s, v; // n 貨品數量, s 體積, v 利潤 while(cin >> n) { int c[M+1]={0}; // 重置所有1維數組值為0 while( n ) { cin >> s >> v; i=M; while( (i-s)>=0 ){ c[i] = max( c[i-s]+v , c[i] ); //選最大的利潤 i--; } n--; } cout << c[M] << endl; } return 0; }