文档介绍：动态规划算法的应用
一、动态规划的概念
近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态 规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推 和建模上了。
要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 )
7
OUTPUT FORMAT
输出划分方案总数，如果不存在则输出0。
SAMPLE OUTPUT (file )
4
参考程序如下：
#include <fstream>
using namespace std;
const unsigned int MAX_SUM = 1024;
int n;
unsigned long long int dyn[MAX_SUM];
ifstream fin ("");
ofstream fout ("");
int main() {
fin >> n;
();
int s = n*(n+1);
if (s % 4) {
fout << 0 << endl;
();
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;
();
return 0;
}
USACO 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 )
A AB BA CA BBC
ABABACABAABC
OUTPUT FORMAT
只有一行，输出一个整数，表示S能够分解成P中元素的最长前缀的长度。
SAMPLE OUTPUT (file ) 11
示例程序如下：
#include <>
#define MAXP 200
#define MAXL 10
char prim[MAXP+1][MAXL+1];
int nump;
int start[200001];
char data[200000];
int ndata;
int main(int argc, char **a