ref：http://topcoder.5d6d.com/thread-75-1-1.html
- 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]; //前i个数中能拼凑出和为j的种数：dyn[ j ] = dyn[ j - i ] + dyn[ j ]
- 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
动规的基本思路：定义f[i]，表示到目标字符串的第i个位置，是否还有连续的前缀。有，则把当前的i+length(si[k])记录下来；没有，则继续循环。Si[k]记录集合中的待选字符串。
- 示例程序如下：
- #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, "%in", 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; // 由于数组元素不减，末元素最大
- }
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
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
设得到一个子序列Qi,Qi+1,Qi+2,…,Qj-2,Qj-1,Qj;
由于后一个人按最佳策略取数,所以他必将取一个最大值f(i+1,j)或f(i,j-1),那么此时取数的人以后取得的数将是sum(i+1,j)-f(i+1,j)或是sum(i,j-1)-f(i,j-1),此时取数的人按最佳策略取数,他会取Qi或者Qj使得sum(i+1,j)-f(i+1,j)+Qi和sum(i,j-1)-f(i,j-1)+Qj二者能有较大值.这样从游戏的结束向游戏的开始推,可以得到总的最优解.
for i←n-1 downto 1 do
for j←i+1 to n do
begin
sum(i,j)←sum(i,j-1)+Qj
f[i,j]←max{sum(i+1,j)+Qi-f(i+1,j),sum(i,j-1)+Qj-f(i,j-1)}
end;
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
- 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
分析 动态规划
f[i, j, k]：前i首歌 前j个光盘 在当前时间限制为k时最多能放多少首歌。
当k>=a[i]时f[i,j,k]=max(f[i-1,j,k-a[i]] + 1, f[i-1,j,k])；当k<a[i]时f[i,j,k]=max(f[i,j-1,t], f[i-1,j,k])
i表示的是第i首歌，j表示的是第j个光盘，k表示的是要用的时间，
a[i]是第i首歌的时间，t表示的是光盘的最大空间。
其实他就是一个01背包类的问题，只不过我们要考虑一下当前的这个光盘是否可以放，然后在考虑放与不放。
#include<stdlib.h>
#include<stdio.h>
int main()
{
int i1,i2,n,t,m,i,a[22],f[50][50][50]={0};
FILE in;
in=fopen("input12.txt","r");
fscanf(in,"%d%d%d",&n,&t,&m);
for(i=1;i<=n;i++)
fscanf(in,"%d",&a[i]);
for(i=1;i<=n;i++)
for(i1=1;i1<=m;i1++)
for(i2=0;i2<=t;i2++)
{
if(i2>=a[i])
{
f[i][i1][i2]=f[i-1][i1][i2];
if(f[i][i1][i2]<f[i-1][i1][i2-a[i]]+1)
f[i][i1][i2]=f[i-1][i1][i2-a[i]]+1;
}
else
{
f[i][i1][i2]=f[i][i1-1][t];
if(f[i][i1][i2]<f[i-1][i1][i2])
f[i][i1][i2]=f[i-1][i1][i2];
}
}
printf("%d",f[n][m][t]);
system("pause");
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－