先尝试过小数据
题目
有8张卡牌，每个卡牌都可以有不同的等级，每个卡牌的不同等级具有不同的攻击力，可以通过花钱给卡牌充值从而升级，且每次只能升一级，比如可以花1个硬币将卡牌2从1级升级到2级，同时卡牌2可以获得更高的攻击力。现在给定8张卡牌的初始等级Li, 和卡牌的最高等级 Ki, 以及每张卡牌的不同等级的攻击力Aij，以及每张卡牌从等级i升级到等级i+1 时候所需要花的硬币，以及玩家手中现有的总硬币数。
求出玩家通过手中的硬币给卡牌升级，可以使得卡牌获得的攻击力的最大值。
分析
很典型的有限背包问题，只需要构造状态 dp[i][j] (前i种卡牌，通过花j个硬币，可以获得攻击力的最大值），有递推公式
for(level = initial_level; level <= max_level; level ++)
dp[i][j] = max{dp[i][j] + dp[i-1][j - sum_cost] + Attack[i][level]}
其中 sum_cost 是指从initial_level到达当前level所花费的总硬币数目；
比赛的时候以为很简单，小数据通过这种动态规划应该可以过，但是中间遇到了好多bug：
（1）声明dp数组的时候脑残的 声明了dp[8][1005]，而其他相关的数组都是声明第一维 至少为10，只有dp数组 第一维被声明成了8，当时一个没注意导致后来不得不在vs中单步debug，而在单步debug的时候发现函数中的某个变量总是莫名其妙的被修改。。百思不得其解，以至于开始怀疑编译器对我不友好== 直到比赛完了之后才发现dp数组的大小声明有误；
麻蛋，这绝对是个大教训！
（2）递归公式很好想，但是边界值在比赛的时候并没有考虑清楚：
边界值应该根据dp状态的定义来谨慎的设置，比如这道题中 dp[i][j] 表示对于前i（1 <= i <= N)种卡牌，使用j个硬币进行增值，所能获得的最大攻击力。于是有
for (int i = 1; i <= N; i++){
attack += A[i - 1][L[i - 1]];
dp[i][0] = attack;
}
同时，在对j的循环中，dp[i][j]的初始值设为 dp[i-1][j] + A[i][initial_level] 表示在对第i种卡牌进行增值的时候，如果不在第i种卡牌花钱增值，此时获得的最大的攻击力为
在前i-1种卡牌上花j个硬币所获得的最大攻击力加上第i种卡牌的初始攻击力.
实现
#include<iostream>
#include<stdio.h>
int dp[10][1005]; int K[10];
int L[10];
int A[10][1005];
int C[10][1005];
int N, M; int getMax(int a, int b){
return a > b ? a : b;
} int Solve(){
memset(dp, 0, sizeof(dp));
int attack = 0;
for (int i = 1; i <= N; i++){
attack += A[i - 1][L[i - 1]];
dp[i][0] = attack;
}
for (int i = 1; i <= N; i++){
int cur_level = L[i-1];
for (int j = 1; j <= M; j++){
int sum_cost = 0, sum_attack = 0;
dp[i][j] = dp[i-1][j] + A[i-1][cur_level];
for (int lev = cur_level; lev < K[i-1]; lev++){
sum_cost += C[i-1][lev];
sum_attack = A[i-1][lev+1];
if (j >= sum_cost)
dp[i][j] = getMax(dp[i][j], dp[i - 1][j - sum_cost] + sum_attack);
}
}
}
return dp[N][M];
} #define FILE_INPUT
int main(){
#ifdef FILE_INPUT
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif
int T;
scanf("%d", &T);
for (int cas = 1; cas <= T; cas++){
fprintf(stderr, "Case #%d processing\n", cas);
scanf("%d %d", &M, &N);
for (int i = 0; i < N; i++){
scanf("%d %d", &K[i], &L[i]);
for (int j = 1; j <= K[i]; j++){
scanf("%d", &A[i][j]);
}
for (int j = 1; j < K[i]; j++){
scanf("%d", &C[i][j]);
}
}
ll result = Solve();
printf("Case #%d: %lld\n", cas, result);
}
return 0;
}