USACO
2.2 Subset Sums
題目如下：
對(duì)于從1到N的連續(xù)整集合合，能劃分成兩個(gè)子集合，且保證每個(gè)集合的數(shù)字和是相等的。
舉個(gè)例子，如果N=3，對(duì)于{1，2，3}能劃分成兩個(gè)子集合，他們每個(gè)的所有數(shù)字和是相等的：
and {1,2}
這是唯一一種分發(fā)（交換集合位置被認(rèn)為是同一種劃分方案，因此不會(huì)增加劃分方案總數(shù)）
如果N=7，有四種方法能劃分集合{1，2，3，4，5，6，7}，每一種分發(fā)的子集合各數(shù)字和是相等的:
{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，你的程序應(yīng)該輸出劃分方案總數(shù)，如果不存在這樣的劃分方案，則輸出0。程序不能預(yù)存結(jié)果直接輸出。
PROGRAM NAME: subset
INPUT FORMAT
輸入文件只有一行，且只有一個(gè)整數(shù)N
SAMPLE INPUT (file subset.in)
7
OUTPUT FORMAT
輸出劃分方案總數(shù)，如果不存在則輸出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
題目如下：
在生物學(xué)中，一些生物的結(jié)構(gòu)是用包含其要素的大寫字母序列來表示的。生物學(xué)家對(duì)于把長的序列分解成較短的（稱之為元素的）序列很感興趣。
如果一個(gè)集合 P 中的元素可以通過串聯(lián)（允許重復(fù)；串聯(lián)，相當(dāng)于 Pascal 中的 “+” 運(yùn)算符）組成一個(gè)序列 S ，那么我們認(rèn)為序列 S 可以分解為 P 中的元素。并不是所有的元素都必須出現(xiàn)。舉個(gè)例子，序列 ABABACABAAB 可以分解為下面集合中的元素：
{A, AB, BA, CA, BBC}
序列 S 的前面 K 個(gè)字符稱作 S 中長度為 K 的前綴。設(shè)計(jì)一個(gè)程序，輸入一個(gè)元素集合以及一個(gè)大寫字母序列，計(jì)算這個(gè)序列最長的前綴的長度。
PROGRAM NAME: prefix
INPUT FORMAT
輸入數(shù)據(jù)的開頭包括 1..200 個(gè)元素（長度為 1..10 ）組成的集合，用連續(xù)的以空格分開的字符串表示。字母全部是大寫，數(shù)據(jù)可能不止一行。元素集合結(jié)束的標(biāo)志是一個(gè)只包含一個(gè) “.” 的行。集合中的元素沒有重復(fù)。接著是大寫字母序列 S ，長度為 1..200,000 ，用一行或者多行的字符串來表示，每行不超過 76 個(gè)字符。換行符并不是序列 S 的一部分。
SAMPLE INPUT (file prefix.in)
A AB BA CA BBC
.
ABABACABAABC
OUTPUT FORMAT
只有一行，輸出一個(gè)整數(shù)，表示 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
題目如下：
我們?cè)囍O(shè)計(jì)我們的競(jìng)賽以便人們能盡可能的多得分,這需要你的幫助。
我們可以從幾個(gè)種類中選取競(jìng)賽的題目,這里的一個(gè)"種類"是指一個(gè)競(jìng)賽題目的集合,解決集合中的題目需要相同多的時(shí)間并且能得到相同的分?jǐn)?shù)。
你的任務(wù)是寫一個(gè)程序來告訴USACO的職員,應(yīng)該從每一個(gè)種類中選取多少題目,使得解決題目的總耗時(shí)在競(jìng)賽規(guī)定的時(shí)間里并且總分最大。
輸入包括競(jìng)賽的時(shí)間,M(1 <= M <= 10,000)和N,"種類"的數(shù)目1 <= N <= 10,000。
后面的每一行將包括兩個(gè)整數(shù)來描述一個(gè)"種類":
第一個(gè)整數(shù)說明解決這種題目能得的分?jǐn)?shù)(1 <= points <= 10000),第二整數(shù)說明解決這種題目所需的時(shí)間(1 <= minutes <= 10000)。
你的程序應(yīng)該確定我們應(yīng)該從每個(gè)"種類"中選多少道題目使得能在競(jìng)賽的時(shí)間中得到最大的分?jǐn)?shù)。
來自任意的"種類"的題目數(shù)目可能任何非負(fù)數(shù)(0或更多)。
計(jì)算可能得到的最大分?jǐn)?shù)。
PROGRAM NAME: inflate
INPUT FORMAT
第 1 行: M, N--競(jìng)賽的時(shí)間和題目"種類"的數(shù)目。
第 2-N+1 行: 兩個(gè)整數(shù):每個(gè)"種類"題目的分?jǐn)?shù)和耗時(shí)。
SAMPLE INPUT (file inflate.in)
300 4
100 60
250 120
120 100
35 20
OUTPUT FORMAT
單獨(dú)的一行包括那個(gè)在給定的限制里可能得到的最大的分?jǐn)?shù)。
SAMPLE OUTPUT (file inflate.out)
605
{從第2個(gè)"種類"中選兩題，第4個(gè)"種類"中選三題}
示例程序如下：
#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; // 由于數(shù)組元素不減，末元素最大
}
USACO 3.3
A Game
題目如下：
有如下一個(gè)雙人游戲:N(2 <= N <= 100)個(gè)正整數(shù)的序列放在一個(gè)游戲平臺(tái)上，兩人輪流從序列的兩端取數(shù)，取數(shù)后該數(shù)字被去掉并累加到本玩家的得分中，當(dāng)數(shù)取盡時(shí)，游戲結(jié)束。以最終得分多者為勝。
編一個(gè)執(zhí)行最優(yōu)策略的程序，最優(yōu)策略就是使自己能得到在當(dāng)前情況下最大的可能的總分的策略。你的程序要始終為第二位玩家執(zhí)行最優(yōu)策略。
PROGRAM NAME: game1
INPUT FORMAT
第一行: 正整數(shù)N, 表示序列中正整數(shù)的個(gè)數(shù)。
第二行至末尾: 用空格分隔的N個(gè)正整數(shù)（大小為1-200）。
SAMPLE INPUT (file game1.in)
6
4 7 2 9
5 2
OUTPUT FORMAT
只有一行，用空格分隔的兩個(gè)整數(shù): 依次為玩家一和玩家二最終的得分。
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
題目如下：
你剛剛得到了流行的“破鑼搖滾”樂隊(duì)錄制的尚未發(fā)表的N(1 <= N <= 20)首歌的版權(quán)。你打算從中精選一些歌曲，發(fā)行M(1 <= M <= 20)張CD。每一張CD最多可以容納T(1 <= T <= 20)分鐘的音樂，一首歌不能分裝在兩張CD中。
不巧你是一位古典音樂迷，不懂如何判定這些歌的藝術(shù)價(jià)值。于是你決定根據(jù)以下標(biāo)準(zhǔn)進(jìn)行選擇：
歌曲必須按照創(chuàng)作的時(shí)間順序在CD盤上出現(xiàn)。
選中的歌曲數(shù)目盡可能地多。
PROGRAM NAME: rockers
INPUT FORMAT
第一行： 三個(gè)整數(shù)：N, T, M.
第二行： N個(gè)整數(shù)，分別表示每首歌的長度，按創(chuàng)作時(shí)間順序排列。
SAMPLE INPUT (file rockers.in)
4 5 2
4 3 4 2
OUTPUT FORMAT
一個(gè)整數(shù)，表示可以裝進(jìn)M張CD盤的樂曲的最大數(shù)目。
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++)/*當(dāng)前cd */
for (b = 0; b <= cdlength; b++) /* 已過的時(shí)間*/
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
“逢低吸納”是炒股的一條成功秘訣。如果你想成為一個(gè)成功的投資者，就要遵守這條秘訣:
"逢低吸納,越低越買"
這句話的意思是：每次你購買股票時(shí)的股價(jià)一定要比你上次購買時(shí)的股價(jià)低.按照這個(gè)規(guī)則購買股票的次數(shù)越多越好，看看你最多能按這個(gè)規(guī)則買幾次。
給定連續(xù)的N天中每天的股價(jià)。你可以在任何一天購買一次股票，但是購買時(shí)的股價(jià)一定要比你上次購買時(shí)的股價(jià)低。寫一個(gè)程序，求出最多能買幾次股票。
以下面這個(gè)表為例, 某幾天的股價(jià)是:
天數(shù) 1 2 3 4 5 6 7 8 9 10 11 12
股價(jià) 68 69 54 64 68 64 70 67 78 62 98 87
這個(gè)例子中, 聰明的投資者(按上面的定義)，如果每次買股票時(shí)的股價(jià)都比上一次買時(shí)低，那么他最多能買4次股票。一種買法如下(可能有其他的買法):
天數(shù) 2 5 6 10
股價(jià) 69 68 64 62
PROGRAM NAME: buylow
INPUT FORMAT
第1行: N (1 <= N <= 5000), 表示能買股票的天數(shù)。
第2行以下: N個(gè)正整數(shù) (可能分多行) ，第i個(gè)正整數(shù)表示第i天的股價(jià). 這些正整數(shù)大小不會(huì)超過longint(pascal)/long(c++).
SAMPLE INPUT (file buylow.in)
12
68 69 54 64 68 64 70 67
78 62 98 87
OUTPUT FORMAT
只有一行，輸出兩個(gè)整數(shù)：
能夠買進(jìn)股票的天數(shù)
長度達(dá)到這個(gè)值的股票購買方案數(shù)量
在計(jì)算解的數(shù)量的時(shí)候，如果兩個(gè)解所組成的字符串相同，那么這樣的兩個(gè)解被認(rèn)為是相同的（只能算做一個(gè)解）。因此，兩個(gè)不同的購買方案可能產(chǎn)生同一個(gè)字符串，這樣只能計(jì)算一次。
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++;
}
/*初始化高精度數(shù)*/
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計(jì)算最大長度*/
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;
}