题目链接：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]的枚举，每次取三个转移方向中最优的那个。
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <string> 5 #include <cstdlib> 6 #include <cctype> 7 #include <cmath> 8 #include <algorithm> 9 #include <vector> 10 #include <map> 11 #include <set> 12 #include <stack> 13 #include <queue> 14 #include <assert.h> 15 #define FREAD(fn) freopen((fn), "r", stdin) 16 #define RINT(vn) scanf("%d", &(vn)) 17 #define PINT(vb) printf("%d", vb) 18 #define RSTR(vn) scanf("%s", (vn)) 19 #define PSTR(vn) printf("%s", (vn)) 20 #define CLEAR(A, X) memset(A, X, sizeof(A)) 21 #define REP(N) for(i=0; i<(N); i++) 22 #define REPE(N) for(i=1; i<=(N); i++) 23 #define pb(X) push_back(X) 24 #define pn() printf("\n") 25 using namespace std; 26 const int MAX_N = 4005; 27 int i, j; 28 int n, a, b, c; 29 int dp[MAX_N];//dp[i]=总长度为i时能切成的最大块数 30 31 int main() 32 { 33 CLEAR(dp, 0); 34 RINT(n); 35 RINT(a); RINT(b); RINT(c); 36 if(a > b) swap(a, b); 37 if(b > c) swap(b, c); 38 for(i=0; i<a; i++) 39 dp[i] = 0; 40 for(i=a; i<b; i++){ 41 if(i % a == 0) dp[i] = i/a; 42 else dp[i] = 0; 43 } 44 for(i=b; i<=c; i++){ 45 if(i % a == 0){ 46 dp[i] = i/a; 47 continue; 48 } 49 else{ 50 bool flag = 0; 51 for(j=0; j*a < i; j++){ 52 if((i-j*a) % b == 0){ 53 flag = 1; 54 dp[i] = max(dp[i], j + (i-j*a)/b); 55 } 56 } 57 if(flag) continue; 58 } 59 if(i % b == 0) dp[i] = max(dp[i], i/b); 60 else if(i == c) dp[i] = max(dp[i], 1); 61 else dp[i] = 0; 62 } 63 //printf("dp[%d] = %d\n", b, dp[b]); 64 for(i=c; i<=n; i++){ 65 if(dp[i-a] > 0) 66 dp[i] = max(dp[i], dp[i-a] + 1); 67 if(dp[i-b] > 0) 68 dp[i] = max(dp[i], dp[i-b] + 1); 69 if(dp[i-c] > 0) 70 dp[i] = max(dp[i], dp[i-c] + 1); 71 } 72 // REP(n) 73 // printf("dp[%d] = %d\n", i, dp[i]); 74 PINT(dp[n]); 75 return 0; 76 }
