题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1013
大三了，准备刷一下动态规划，保持思维的灵活性，这一次从zoj刷起，一道道刷，今天是9月29日，这是第一道。
这一道题目很长，题意：有n辆车，有三种材料，每种材料有独特的两种属性w，s，和一种防御值，按照题意，取几个组合可以形成一个comb，获得组合防御值（原先的不算了），每辆车也有w，s限制，求最大的防御值（所有材料每个小于500）
这道题有两个限制条件w，s，很容易想到二维背包，但是有三种材料，如果f[i][w][s]取得是防御值的话，那么组合，材料选取，情况将很复杂，然而组合的和每辆车的情况无关，只和总情况有关，所以定义f[i][j][k]为前i辆车取了j个头盔，k个铠甲时最大可取的靴子数量，先把所有可能情况dp统计出来，因为数据范围比较小，材料小于500，相当于带减枝的搜索。
可以使用滚动数组节省空间，转移方程f[i][j+k1][k+k2]=max(f[1-i][j][k]+cal(i,k1,k2)),转移时因为最大可取的靴子数为0也是合法的一种情况，所以我们需要把不合法（或者初始不确定情况）定义为-1；
这道题的关键在于状态的定义，滚动数组也熟悉了使用了一下。
130ms
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
int w1,s1,c1,w2,s2,c2,w3,s3,c3,g1,g2,g3,all,n;
struct big
{
int w,s;
}hh[];
int f[][][]; void read()
{
cin>>w1>>s1>>c1;
cin>>w2>>s2>>c2;
cin>>w3>>s3>>c3;
cin>>g1>>g2>>g3>>all;
for(int i=;i<n;i++)
{
cin>>hh[i].w>>hh[i].s;
}
} void solve()
{
memset(f,,sizeof(f));
int ans1=,ans2=,ans=;
for(int k=;k<n;k++)
{
int ansx=ans1;
int ansy=ans2;
memset(f[ans],-,sizeof(f[ans]));
for(int i=;i<=ans1;i++)
{
for(int j=;j<=ans2;j++)
{
if(f[-ans][i][j]!=-)
{
for(int k1=;k1*w1<=hh[k].w&&k1*s1<=hh[k].s;k1++)
{
int t1=hh[k].w-k1*w1;
int t2=hh[k].s-k1*s1;
for(int k2=;k2*w2<=t1&&k2*s2<=t2;k2++)
{
int tt=min((t1-k2*w2)/w3,(t2-k2*s2)/s3);
f[ans][i+k1][j+k2]=max(f[ans][i+k1][j+k2],f[-ans][i][j]+tt);
ansx=max(ansx,i+k1);
ansy=max(ansy,j+k2);
}
}
} }
}
ans1=ansx;
ans2=ansy;
ans=-ans;
}
ans=-ans;
int res=;
for(int i=;i<=ans1;i++)
for(int j=;j<=ans2;j++)
{
int xx=f[ans][i][j];
if(xx==-)
continue;
if(g1*c1+g2*c2+g3*c3>=all)
{
res=max(res,i*c1+j*c2+xx*c3);
}
else
{
int yy=min(i/g1,min(j/g2,xx/g3));
res=max(res,yy*all+(i-yy*g1)*c1+(j-yy*g2)*c2+(xx-yy*g3)*c3);
}
}
printf("%d\n",res);
}
int main()
{
//freopen("input.txt","r",stdin);
int cas=;
while(cin>>n&&n)
{
if(cas>)
puts("");
printf("Case %d: ",cas++);
read();
solve();
}
}