题目链接：http://codeforces.com/problemset/problem/189/A
题意：一个长度为n的纸带，允许切割若干次，每次切下的长度只能是{a, b, c}之一。问最多能切成多少块。
思路：动态规划，记dp[i] 为当前已经切下总长度 i 时最多能切成的块数，即规模为 i 的子问题。
状态的转移比较好想，每次只可能从dp[i-a], dp[i-b], dp[i-c]三个方向通过加一转移过来。
问题的初始化我考虑得有点复杂：先把a, b, c从小到大排序，然后对于 i 属于[0, a), [a, b), [b, c]三个区间按顺序初始化dp[i]：判断 i 能否分解成{a}, {a, b}, {a, b, c}的“线性组合”，可以的话取系数和最大的那个作为dp[i]。
初始化之后就是线性的从[c, n]的枚举，每次取三个转移方向中最优的那个。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <assert.h>
#define FREAD(fn) freopen((fn), "r", stdin)
#define RINT(vn) scanf("%d", &(vn))
#define PINT(vb) printf("%d", vb)
#define RSTR(vn) scanf("%s", (vn))
#define PSTR(vn) printf("%s", (vn))
#define CLEAR(A, X) memset(A, X, sizeof(A))
#define REP(N) for(i=0; i<(N); i++)
#define REPE(N) for(i=1; i<=(N); i++)
#define pb(X) push_back(X)
#define pn() printf("\n")
using namespace std;
const int MAX_N = ;
int i, j;
int n, a, b, c;
int dp[MAX_N];//dp[i]=总长度为i时能切成的最大块数 int main()
{
CLEAR(dp, );
RINT(n);
RINT(a); RINT(b); RINT(c);
if(a > b) swap(a, b);
if(b > c) swap(b, c);
for(i=; i<a; i++)
dp[i] = ;
for(i=a; i<b; i++){
if(i % a == ) dp[i] = i/a;
else dp[i] = ;
}
for(i=b; i<=c; i++){
if(i % a == ){
dp[i] = i/a;
continue;
}
else{
bool flag = ;
for(j=; j*a < i; j++){
if((i-j*a) % b == ){
flag = ;
dp[i] = max(dp[i], j + (i-j*a)/b);
}
}
if(flag) continue;
}
if(i % b == ) dp[i] = max(dp[i], i/b);
else if(i == c) dp[i] = max(dp[i], );
else dp[i] = ;
}
//printf("dp[%d] = %d\n", b, dp[b]);
for(i=c; i<=n; i++){
if(dp[i-a] > )
dp[i] = max(dp[i], dp[i-a] + );
if(dp[i-b] > )
dp[i] = max(dp[i], dp[i-b] + );
if(dp[i-c] > )
dp[i] = max(dp[i], dp[i-c] + );
}
// REP(n)
// printf("dp[%d] = %d\n", i, dp[i]);
PINT(dp[n]);
return ;
}