题意:表达能力不好,就不说了。
分析:算是比较简单的背包了,f[i][j][k]表示前i辆车装了j个武器1和k个武器2后还能装武器3的最多个数,再转移即可。
#include <iostream>
#include 
<stdio.h>
#include 
<memory.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))

int f[2][510][510],w[4],s[4],d[4],x[110],y[110],n;

int main()
{
    
int i,j,k,now,pre,tem,c1,c2,c3,d4,ca=0,p,q,rew,res;
    
int last1,last2,up1,up2;
    
while(scanf("%d",&n)&&n)
    
{
        
if(ca>0) printf("\n");
        
for(i=1;i<=3;i++) scanf("%d%d%d",&w[i],&s[i],&d[i]);
        scanf(
"%d%d%d%d",&c1,&c2,&c3,&d4);
        
for(i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
        memset(f,
-1,sizeof(f));
        f[
0][0][0]=0;
        now
=1; pre=0
        last1
=0; last2=0;
        
for(i=1;i<=n;i++)
        
{
            up1
=last1+min(x[i]/w[1],y[i]/s[1]);  // 加点小优化减少决策范围 从5000ms减到500ms
            if(up1>500) up1=500;
            up2
=last2+min(x[i]/w[2],y[i]/s[2]); 
            
if(up2>500) up2=500;
            
for(j=0;j<=up1;j++)
            
{
                
for(k=0;k<=up2;k++)
                
{
                    f[now][j][k]
=-1;
                    
for(p=0;p<=j;p++)
                    
{
                        
if(p*w[1]>x[i]||p*s[1]>y[i]) break;
                        
for(q=0;q<=k;q++)
                        
{
                            
if(p*w[1]+q*w[2]>x[i]||p*s[1]+q*s[2]>y[i]) break;
                            
if(f[pre][j-p][k-q]==-1continue;
                            rew
=x[i]-p*w[1]-q*w[2];
                            res
=y[i]-p*s[1]-q*s[2];
                            tem
=min(rew/w[3],res/s[3]); // 当前这辆车装完p个武器1和q个武器2后还能装武器3的个数
                            if(f[pre][j-p][k-q]+tem>f[now][j][k])
                                f[now][j][k]
=f[pre][j-p][k-q]+tem;
                        }

                    }

                    
if(f[now][j][k]!=-1)
                    
{
                        last1
=max(last1,j);
                        last2
=max(last2,k);
                    }

                }

            }

            tem
=now; now=pre; pre=tem;
        }

        
int flag,ans=0,num;
        
if(c1*d[1]+c2*d[2]+c3*d[3]>d4) flag=1;  // 选择比较好的组合武器的方式
        else flag=2;
        
for(i=0;i<=500;i++)
        
{
            
for(j=0;j<=500;j++)
            
{
                
if(f[pre][i][j]==-1continue;
                k
=f[pre][i][j];
                
if(flag==1)
                    ans
=max(ans,i*d[1]+j*d[2]+k*d[3]);
                
else
                
{
                    num
=min(i/c1,min(j/c2,k/c3));
                    tem
=num*d4+(i-num*c1)*d[1]+(j-num*c2)*d[2]+(k-num*c3)*d[3];
                    ans
=max(ans,tem);
                }

            }

        }

        printf(
"Case %d: %d\n",++ca,ans);
    }

    
return 0;
}