[ZJ] a758 二、營救夥伴、a759 三、N進位、a763 pB. Shark 的數學遊戲
內容 ：
珍珍被惡魔黨抓走了，經過在山區一連串的偵查與探索，鐵雄在一個隱密的山洞裡總算找到了珍珍。但是，惡魔黨也不是省油的燈，精心設計了機關把珍珍與炸彈開關綑綁在一起了，鐵雄必須解除機關開關才能順利撘救珍珍。
該機關是一個磅秤，旁邊有N個法碼，每個法碼的重量皆不相同，鐵雄必須由這些法碼中選取數個置於磅秤上使總重量吻合炸彈重量W，才可解除機關開關。在這緊張的關頭上，能冷靜的計算出合適的法碼組合，已經是夠令人喘不過氣來的，更棘手的是，鐵雄在每取用一個法碼時，身體將感受到來自法碼的高壓電擊，感到極端痛苦。
加油！我們來替鐵雄算出可行的法碼重量組合，同時，取用的法碼數量是最少的。
輸入說明 ：
輸入檔中的第一行，為二個正整數W、N，代表炸彈重量與法碼個數，數值範圍為W<=2000、N<=50。第二行則有N個正整數，代表每個法碼的重量T，T<=200。
同一行的數字，彼此之間皆用一個空白格開。
輸出說明 ：
第一行有二個數字，依序為最少法碼數量Q與所有符合的法碼重量組合數S。接下來的S行中，每一行有Q個法碼重量，以小到大依序列出。
同一行的數字，彼此之間皆用一個空白格開。
有至少1組是符合的法碼重量組合的。
100 7 10 20 30 25 40 35 50
範例輸出 ：
3 3 10 40 50 20 30 50 25 35 40
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
int w, n;
int a[55], dp[55][2000];
int path[55];
vector< vector<int> > ret;
void dfs(int n, int w, int dep) {
if(n == 0) {
vector<int> buf;
for(int i = dep-1; i >= 0; i--)
buf.push_back(path[i]);
ret.push_back(buf);
return ;
}
if(dp[n][w] == dp[n-1][w])
dfs(n-1, w, dep);
if(w-a[n] >= 0 && dp[n][w] == dp[n-1][w-a[n]]+1) {
path[dep] = a[n];
dfs(n-1, w-a[n], dep+1);
}
}
int main() {
int i, j;
while(scanf("%d %d", &w, &n) == 2) {
for(i = 1; i <= n; i++)
scanf("%d", &a[i]);
sort(a+1, a+1+n);
memset(dp, 63, sizeof(dp));
dp[0][0] = 0;
for(i = 1; i <= n; i++) {
for(j = 0; j <= w; j++) {
dp[i][j] = dp[i-1][j];
if(j - a[i] >= 0)
dp[i][j] = min(dp[i][j], dp[i-1][j-a[i]]+1);
}
}
ret.clear();
dfs(n, w, 0);
sort(ret.begin(), ret.end());
printf("%d %d\n", dp[n][w], ret.size());
for(i = 0; i < ret.size(); i++) {
vector<int> &v = ret[i];
for(j = 0; j < v.size(); j++)
printf("%d%c", v[j], j != v.size()-1 ? ' ' : '\n');
}
}
return 0;
}
內容 ：
高一資訊科技概論裡介紹了2進位數字系統，也說明了2進位與10進位的轉換方法。現在，想像我們來到了一個異想世界，該世界的人們所用的是N進位數字系統，N並沒有統一，有的人用10進位、有的人用2進位、也有人用7進位，哇，好複雜！
異想世界舉辦樂透活動，中獎規則是：彩券上的號碼為”N進位數字A”，與開獎號碼”10進位數字B”相加後轉換為”2進位數字C”，接著，計算C裡的所有位數的和為”10進位數字S”，S最大者就是幸運兒囉，所有幸運兒平分該次獎金！對了，要成為幸運兒，還有一個條件：A必須小於B。
我們一起來算算本次樂透活動共有幾位幸運兒獲獎。
輸入說明 ：
輸入檔中的第一行，有一個10進位整數，為開獎號碼B；第二行，有一個10進位數字，為購買彩券的人數D(每人限購1張)；接下來的D行，每行有兩個正整數N與A，分別代表彩券上的N進位與簽注數字A。
數字範圍(以10進位表示)：10000<=B<=999999；5<=D<=20；2<=N<=16；10000<=A<=999999。
同一行的數字，彼此之間皆用一個空白格開。
輸出說明 ：
第一行，輸出二個數字，分別為最大的S與幸運兒的人數。
以10進位表示，同一行的數字，彼此之間皆用一個空白格開。
888888 5 2 11011111111000000000 7 554212 8 1274233 10 98261 16 ABC27
範例輸出 ：
11 2
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
int B;
int n, i, j, k;
while(scanf("%d", &B) == 1) {
scanf("%d", &n);
int w[30], choose = 0;
for(i = 0; i < n; i++) {
int d, number = 0;
char s[105];
scanf("%d %s", &d, s);
for(j = 0; s[j]; j++) {
number = number * d;
if(s[j] >= '0' && s[j] <= '9')
number += s[j] - '0';
else
number += s[j] - 'A' + 10;
}
w[i] = 0;
if(number >= B)
continue;
number += B;
for(j = 0; j < 32; j++)
if((number>>j)&1)
w[i]++;
choose = max(choose, w[i]);
}
int cnt = 0;
for(i = 0; i < n; i++)
cnt += w[i] == choose;
printf("%d %d\n", choose, cnt);
}
return 0;
}
內容 ：
鯊魚(英文名字Shark)是一位從來不哭的男孩，有一天，他閒的發慌，發明了一個打發時間的數學遊戲。
規則是這樣的:
給兩個正整數 N , M ，代表有 N 個數字， 我們要將他們分成 M ( M <= N ) 個區塊，使計算後出來的值最小。
遊戲怎麼玩呢? 來看看下面的例子:
當 N = 5 , M = 3 ， 且輸入的五個數字分別為 0.5 , 0.4 , 0.4 , 0.3 , 0.2 ，我們要將這數列切成三份，
如果我這樣切 0.5 | 0.4 0.4 | 0.3 0.2
區段編號 1 2 3
計算方法為 區段1個數 * 區段1和 + (區段1個數+區段2個數) *區段2和 + (區段1個數+區段2個數+區段3個數) *區段3和
則計算出來的結果為 [1 * 0.5] + [(1+2) * (0.4+0.4)] + [(1+2+2)*(0.3+0.2)] = 5.4
如果我這樣切 0.5 | 0.4 | 0.4 0.3 0.2
則計算出來的結果為 [1 * 0.5] + [(1+1) * (0.4)] + [(1+1+3)*(0.4+0.3+0.2)] = 5.8
Shark 想要知道可以玩出的最小值是多少
輸入說明 ：
單筆測資輸入
每一行有兩個正整數 N , M ( M <= N )
接下來有 N 個 < 1 且 >= 0 的小數,至多小數後1位
輸出說明 ：
5 3 0.5 0.4 0.4 0.3 0.2
範例輸出 ：
5.4
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
double dp[2024][105];
int main() {
int n, m;
int i, j, k, a, b;
double A[2024], sum[2024];
while(scanf("%d %d", &n, &m) == 2) {
sum[0] = 0;
for(i = 1; i <= n; i++) {
scanf("%lf", &A[i]);
sum[i] = sum[i-1] + A[i];
}
for(int i = 0; i <= n; i++)
for(int j = 0; j <= m; j++)
dp[i][j] = 1e+30;
dp[0][0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
for(int k = i; k >= 1; k--) {
dp[i][j] = min(dp[i][j],
dp[k-1][j-1] + (sum[i]-sum[k-1]) * i);
}
}
}
printf("%.1lf\n", dp[n][m]);
}
return 0;
}