USACO
2.2 Subset Sums
題目如下：
對于從1到N的連續整集合合，能劃分成兩個子集合，且保證每個集合的數字和是相等的。
舉個例子，如果N=3，對于{1，2，3}能劃分成兩個子集合，他們每個的所有數字和是相等的：
and {1,2}
這是唯一一種分發（交換集合位置被認為是同一種劃分方案，因此不會增加劃分方案總數）
如果N=7，有四種方法能劃分集合{1，2，3，4，5，6，7}，每一種分發的子集合各數字和是相等的:
{1,6,7} and {2,3,4,5} {注 1+6+7=2+3+4+5}
{2,5,7} and {1,3,4,6}
{3,4,7} and {1,2,5,6}
{1,2,4,7} and {3,5,6}
給出N，你的程序應該輸出劃分方案總數，如果不存在這樣的劃分方案，則輸出0。程序不能預存結果直接輸出。
PROGRAM NAME: subset
INPUT FORMAT
輸入文件只有一行，且只有一個整數N
SAMPLE INPUT (file subset.in)
7
OUTPUT FORMAT
輸出劃分方案總數，如果不存在則輸出0。
SAMPLE OUTPUT (file subset.out)
4
參考程序如下：
#include <fstream>
using namespace std;
const unsigned int MAX_SUM = 1024;
int n;
unsigned long long int dyn[MAX_SUM];
ifstream fin ("subset.in");
ofstream fout ("subset.out");
int main() {
fin >> n;
fin.close();
int s = n*(n+1);
if (s % 4) {
fout << 0 << endl;
fout.close ();
return ;
}
s /= 4;
int i, j;
dyn [0] = 1;
for (i = 1; i <= n; i++)
for (j = s; j >= i; j--)
dyn[j] += dyn[j-i];
fout << (dyn[s]/2) << endl;
fout.close();
return 0;
}
USACO 2.3
Longest Prefix
題目如下：
在生物學中，一些生物的結構是用包含其要素的大寫字母序列來表示的。生物學家對于把長的序列分解成較短的（稱之為元素的）序列很感興趣。
如果一個集合 P 中的元素可以通過串聯（允許重復；串聯，相當于 Pascal 中的 “+” 運算符）組成一個序列 S ，那么我們認為序列 S 可以分解為 P 中的元素。并不是所有的元素都必須出現。舉個例子，序列 ABABACABAAB 可以分解為下面集合中的元素：
{A, AB, BA, CA, BBC}
序列 S 的前面 K 個字符稱作 S 中長度為 K 的前綴。設計一個程序，輸入一個元素集合以及一個大寫字母序列，計算這個序列最長的前綴的長度。
PROGRAM NAME: prefix
INPUT FORMAT
輸入數據的開頭包括 1..200 個元素（長度為 1..10 ）組成的集合，用連續的以空格分開的字符串表示。字母全部是大寫，數據可能不止一行。元素集合結束的標志是一個只包含一個 “.” 的行。集合中的元素沒有重復。接著是大寫字母序列 S ，長度為 1..200,000 ，用一行或者多行的字符串來表示，每行不超過 76 個字符。換行符并不是序列 S 的一部分。
SAMPLE INPUT (file prefix.in)
A AB BA CA BBC
.
ABABACABAABC
OUTPUT FORMAT
只有一行，輸出一個整數，表示 S 能夠分解成 P 中元素的最長前綴的長度。
SAMPLE OUTPUT (file prefix.out)
11
示例程序如下：
#include <stdio.h>
/* maximum number of primitives */
#define MAXP 200
/* maximum length of a primitive */
#define MAXL 10
char prim[MAXP+1][MAXL+1]; /* primitives */
int nump; /* number of primitives */
int start[200001]; /* is this prefix of the sequence expressible? */
char data[200000]; /* the sequence */
int ndata; /* length of the sequence */
int main(int argc, char **argv)
{
FILE *fout, *fin;
int best;
int lv, lv2, lv3;
if ((fin = fopen("prim.in", "r")) == NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout = fopen("prim.out", "w")) == NULL)
{
perror ("fopen fout");
exit(1);
}
/* read in primitives */
while (1)
{
fscanf (fin, "%s", prim[nump]);
if (prim[nump][0] != '.') nump++;
else break;
}
/* read in string, one line at a time */
ndata = 0;
while (fscanf (fin, "%s", data+ndata) == 1)
ndata += strlen(data+ndata);
start[0] = 1;
best = 0;
for (lv = 0; lv < ndata; lv++)
if (start[lv])
{ /* for each expressible prefix */
best = lv; /* we found a longer expressible prefix! */
/* for each primitive, determine the the sequence starting at
this location matches it */
for (lv2 = 0; lv2 < nump; lv2++)
{
for (lv3 = 0; lv + lv3 < ndata && prim[lv2][lv3] &&
prim[lv2][lv3] == data[lv+lv3]; lv3++)
;
if (!prim[lv2][lv3]) /* it matched! */
start[lv + lv3] = 1; /* so the expanded prefix is also expressive */
}
}
/* see if the entire sequence is expressible */
if (start[ndata]) best = ndata;
fprintf (fout, "%i\n", best);
return 0;
}
USACO 3.1
Score Inflation
題目如下：
我們試著設計我們的競賽以便人們能盡可能的多得分,這需要你的幫助。
我們可以從幾個種類中選取競賽的題目,這里的一個"種類"是指一個競賽題目的集合,解決集合中的題目需要相同多的時間并且能得到相同的分數。
你的任務是寫一個程序來告訴USACO的職員,應該從每一個種類中選取多少題目,使得解決題目的總耗時在競賽規定的時間里并且總分最大。
輸入包括競賽的時間,M(1 <= M <= 10,000)和N,"種類"的數目1 <= N <= 10,000。
后面的每一行將包括兩個整數來描述一個"種類":
第一個整數說明解決這種題目能得的分數(1 <= points <= 10000),第二整數說明解決這種題目所需的時間(1 <= minutes <= 10000)。
你的程序應該確定我們應該從每個"種類"中選多少道題目使得能在競賽的時間中得到最大的分數。
來自任意的"種類"的題目數目可能任何非負數(0或更多)。
計算可能得到的最大分數。
PROGRAM NAME: inflate
INPUT FORMAT
第 1 行: M, N--競賽的時間和題目"種類"的數目。
第 2-N+1 行: 兩個整數:每個"種類"題目的分數和耗時。
SAMPLE INPUT (file inflate.in)
300 4
100 60
250 120
120 100
35 20
OUTPUT FORMAT
單獨的一行包括那個在給定的限制里可能得到的最大的分數。
SAMPLE OUTPUT (file inflate.out)
605
{從第2個"種類"中選兩題，第4個"種類"中選三題}
示例程序如下：
#include <fstream.h>
ifstream fin("inflate.in");
ofstream fout("inflate.out");
const short maxm = 10010;
long best[maxm], m, n;
void
main()
{
short i, j, len, pts;
fin >> m >> n;
for (j = 0; j <= m; j++)
best[j] = 0;
for (i = 0; i < n; i++) {
fin >> pts >> len;
for (j = len; j <= m; j++)
if (best[j-len] + pts > best[j])
best[j] = best[j-len] + pts;
}
fout << best[m] << endl; // 由于數組元素不減，末元素最大
}
USACO 3.3
A Game
題目如下：
有如下一個雙人游戲:N(2 <= N <= 100)個正整數的序列放在一個游戲平臺上，兩人輪流從序列的兩端取數，取數后該數字被去掉并累加到本玩家的得分中，當數取盡時，游戲結束。以最終得分多者為勝。
編一個執行最優策略的程序，最優策略就是使自己能得到在當前情況下最大的可能的總分的策略。你的程序要始終為第二位玩家執行最優策略。
PROGRAM NAME: game1
INPUT FORMAT
第一行: 正整數N, 表示序列中正整數的個數。
第二行至末尾: 用空格分隔的N個正整數（大小為1-200）。
SAMPLE INPUT (file game1.in)
6
4 7 2 9
5 2
OUTPUT FORMAT
只有一行，用空格分隔的兩個整數: 依次為玩家一和玩家二最終的得分。
SAMPLE OUTPUT (file game1.out)
18 11
參考程序如下：
#include <stdio.h>
#define NMAX 101
int best[NMAX][2], t[NMAX];
int n;
void
readx () {
int i, aux;
freopen ("game1.in", "r", stdin);
scanf ("%d", &n);
for (i = 1; i <= n; i++) {
scanf ("%d", &aux);
t = t[i - 1] + aux;
}
fclose (stdin);
}
inline int
min (int x, int y) {
return x > y ? y : x;
}
void
solve () {
int i, l;
for (l = 1; l <= n; l++)
for (i = 1; i + l <= n + 1; i++)
best[l%2] = t[i + l - 1] - t[i - 1] - min (best[i + 1][(l - 1) % 2],
best[(l - 1) % 2]);
}
void writex () {
freopen ("game1.out", "w", stdout);
printf ("%d %d\n", best[1][n % 2], t[n] - best[1][n % 2]);
fclose (stdout);
}
int
main () {
readx ();
solve ();
writex ();
return 0;
}
USACO 3.4
Raucous Rockers
題目如下：
你剛剛得到了流行的“破鑼搖滾”樂隊錄制的尚未發表的N(1 <= N <= 20)首歌的版權。你打算從中精選一些歌曲，發行M(1 <= M <= 20)張CD。每一張CD最多可以容納T(1 <= T <= 20)分鐘的音樂，一首歌不能分裝在兩張CD中。
不巧你是一位古典音樂迷，不懂如何判定這些歌的藝術價值。于是你決定根據以下標準進行選擇：
歌曲必須按照創作的時間順序在CD盤上出現。
選中的歌曲數目盡可能地多。
PROGRAM NAME: rockers
INPUT FORMAT
第一行： 三個整數：N, T, M.
第二行： N個整數，分別表示每首歌的長度，按創作時間順序排列。
SAMPLE INPUT (file rockers.in)
4 5 2
4 3 4 2
OUTPUT FORMAT
一個整數，表示可以裝進M張CD盤的樂曲的最大數目。
SAMPLE OUTPUT (file rockers.out)
3
參考程序如下：
#include <stdio.h>
#define MAX 25
int dp[MAX][MAX][MAX], length[MAX];
int
main ()
{
FILE *in = fopen ("rockers.in", "r");
FILE *out = fopen ("rockers.out", "w");
int a, b, c, d, best, numsongs, cdlength, numcds;
fscanf (in, "%d%d%d", &numsongs, &cdlength, &numcds);
for (a = 1; a <= numsongs; a++)
fscanf (in, "%d", &length[a]);
best = 0;
for (a = 0; a < numcds; a++)/*當前cd */
for (b = 0; b <= cdlength; b++) /* 已過的時間*/
for (c = 0; c <= numsongs; c++) { /* 上一曲*/
for (d = c + 1; d <= numsongs; d++) { /* 下一曲*/
if (b + length[d] <= cdlength) {
if (dp[a][c] + 1 > dp[a][b + length[d]][d])
dp[a][b + length[d]][d] = dp[a][c] + 1;
}
else {
if (dp[a][c] + 1 > dp[a + 1][length[d]][d])
dp[a + 1][length[d]][d] = dp[a][c] + 1;
}
}
if (dp[a][c] > best)
best = dp[a][c];
}
fprintf (out, "%d\n", best);
return 0;
}
USACO
4.3 Buy Low, Buy Lower
“逢低吸納”是炒股的一條成功秘訣。如果你想成為一個成功的投資者，就要遵守這條秘訣:
"逢低吸納,越低越買"
這句話的意思是：每次你購買股票時的股價一定要比你上次購買時的股價低.按照這個規則購買股票的次數越多越好，看看你最多能按這個規則買幾次。
給定連續的N天中每天的股價。你可以在任何一天購買一次股票，但是購買時的股價一定要比你上次購買時的股價低。寫一個程序，求出最多能買幾次股票。
以下面這個表為例, 某幾天的股價是:
天數 1 2 3 4 5 6 7 8 9 10 11 12
股價 68 69 54 64 68 64 70 67 78 62 98 87
這個例子中, 聰明的投資者(按上面的定義)，如果每次買股票時的股價都比上一次買時低，那么他最多能買4次股票。一種買法如下(可能有其他的買法):
天數 2 5 6 10
股價 69 68 64 62
PROGRAM NAME: buylow
INPUT FORMAT
第1行: N (1 <= N <= 5000), 表示能買股票的天數。
第2行以下: N個正整數 (可能分多行) ，第i個正整數表示第i天的股價. 這些正整數大小不會超過longint(pascal)/long(c++).
SAMPLE INPUT (file buylow.in)
12
68 69 54 64 68 64 70 67
78 62 98 87
OUTPUT FORMAT
只有一行，輸出兩個整數：
能夠買進股票的天數
長度達到這個值的股票購買方案數量
在計算解的數量的時候，如果兩個解所組成的字符串相同，那么這樣的兩個解被認為是相同的（只能算做一個解）。因此，兩個不同的購買方案可能產生同一個字符串，這樣只能計算一次。
SAMPLE OUTPUT (file buylow.out)
4 2
參考程序如下：
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct BIGNUM *bignum_t;
struct BIGNUM
{
int val;
bignum_t next;
};
int num[5000];
int len[5000];
int nlen;
bignum_t cnt[5000];
bignum_t get_big(void)
{
static bignum_t block;
static int size = 0;
if (size == 0)
{
block = (bignum_t)malloc(sizeof(*block)*128);
size = 128;
}
size--;
return block++;
}
/*初始化高精度數*/
void init_big(bignum_t *num, int val)
{
*num = get_big();
/* initialize */
(*num)->val = val;
(*num)->next = NULL;
}
void add(bignum_t a, bignum_t b)
{
int c; /* carry */
c = 0;
while (b || c)
{
a->val += c;
if (b) a->val += b->val;
/* if a->val is too large, we need to carry */
c = (a->val / 1000000);
a->val = (a->val % 1000000);
if (b) b = b->next;
if (!a->next && (b || c))
{ /* allocate if we need to */
a->next = get_big();
a = a->next;
a->val = 0;
a->next = NULL;
} else a = a->next;
}
}
void out_num(FILE *f, bignum_t v)
{
if (v->next)
{
out_num(f, v->next);
fprintf (f, "%06i", v->val);
}
else
fprintf (f, "%i", v->val);
}
int main(int argc, char **argv)
{
FILE *fout, *fin;
int lv, lv2;
int c;
int max;
int l;
bignum_t ans;
if ((fin = fopen("buylow.in", "r")) == NULL)
{
perror ("fopen fin");
exit(1);
}
if ((fout = fopen("buylow.out", "w")) == NULL)
{
perror ("fopen fout");
exit(1);
}
fscanf (fin, "%d", &nlen);
for (lv = 0; lv < nlen; lv++)
fscanf (fin, "%d", &num[lv]);
/* 用DP計算最大長度*/
for (lv = 0; lv < nlen; lv++)
{
max = 1;
for (lv2 = lv-1; lv2 >= 0; lv2--)
if (num[lv2] > num[lv] && len[lv2]+1 > max) max = len[lv2]+1;
len[lv] = max;
}
for (lv = 0; lv < nlen; lv++)
{
if (len[lv] == 1) init_big(&cnt[lv], 1);
else
{
init_big(&cnt[lv], 0);
l = -1;
max = len[lv]-1;
for (lv2 = lv-1; lv2 >= 0; lv2--)
if (len[lv2] == max && num[lv2] > num[lv] && num[lv2] != l)
add(cnt[lv], cnt[lv2]);
l = num[lv2];
}
}
}
/* 找最長串*/
max = 0;
for (lv = 0; lv < nlen; lv++)
if (len[lv] > max) max = len[lv];
init_big(&ans, 0);
l = -1;
for (lv = nlen-1; lv >= 0; lv--)
if (len[lv] == max && num[lv] != l)
{
add(ans, cnt[lv]);
l = num[lv];
}
/* output answer */
fprintf (fout, "%i ", max);
out_num(fout, ans);
fprintf (fout, "\n");
return 0;
}